Sorting in Practice — Library Functions

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27

# Python uses Timsort for all sorting operations
import random
 
# Example 1: Sorting a simple list
numbers = [3, 1, 4, 1, 5, 9, 2, 6, 5, 3, 5]
numbers.sort()  # In-place sort using Timsort
print(numbers)  # [1, 1, 2, 3, 3, 4, 5, 5, 5, 6, 9]
 
# Example 2: sorted() returns a new list (non-mutating)
original = [64, 34, 25, 12, 22, 11, 90]
sorted_copy = sorted(original)
print(original)     # [64, 34, 25, 12, 22, 11, 90] - unchanged
print(sorted_copy)  # [11, 12, 22, 25, 34, 64, 90] - sorted
 
# Example 3: Timsort excels on partially sorted data
# This will be FASTER than sorting random data of the same size
nearly_sorted = list(range(1000)) + [random.randint(0, 999) for _ in range(10)]
nearly_sorted.sort()  # Timsort detects the long run at the start
 
# Example 4: Reversing efficiently
descending = sorted(numbers, reverse=True)
print(descending)  # [9, 6, 5, 5, 5, 4, 3, 3, 2, 1, 1]
 
# Example 5: Sorting by key
words = ["banana", "apple", "Cherry", "date"]
sorted_words = sorted(words, key=str.lower)  # Case-insensitive sort
print(sorted_words)  # ['apple', 'banana', 'Cherry', 'date']

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38

#include <algorithm>
#include <vector>
#include <iostream>
#include <functional>  // for std::greater
 
int main() {
    // Example 1: Basic sorting
    std::vector<int> numbers = {3, 1, 4, 1, 5, 9, 2, 6, 5, 3, 5};
    std::sort(numbers.begin(), numbers.end());
    // numbers is now: {1, 1, 2, 3, 3, 4, 5, 5, 5, 6, 9}
    
    // Example 2: Sorting in descending order
    std::sort(numbers.begin(), numbers.end(), std::greater<int>());
    // numbers is now: {9, 6, 5, 5, 5, 4, 3, 3, 2, 1, 1}
    
    // Example 3: Partial sorting (only first k elements sorted)
    std::vector<int> data = {5, 3, 8, 4, 2, 7, 1, 9, 6};
    std::partial_sort(data.begin(), data.begin() + 3, data.end());
    // First 3 elements are the smallest, sorted: {1, 2, 3, ...}
    // Remaining elements are in unspecified order
    
    // Example 4: Finding nth element without full sort
    std::vector<int> data2 = {5, 3, 8, 4, 2, 7, 1, 9, 6};
    std::nth_element(data2.begin(), data2.begin() + 4, data2.end());
    // Element at position 4 is what would be there if sorted
    // All elements before are <= it, all after are >= it
    
    // Example 5: Stable sort (preserves order of equal elements)
    std::vector<std::pair<int, char>> pairs = {
        {3, 'a'}, {1, 'b'}, {3, 'c'}, {2, 'd'}, {1, 'e'}
    };
    std::stable_sort(pairs.begin(), pairs.end(),
        [](const auto& a, const auto& b) { return a.first < b.first; });
    // Result: {1,'b'}, {1,'e'}, {2,'d'}, {3,'a'}, {3,'c'}
    // Note: 'b' stays before 'e', 'a' stays before 'c'
    
    return 0;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62

import java.util.Arrays;
import java.util.Comparator;
import java.util.Collections;
import java.util.List;
import java.util.ArrayList;
 
public class SortingExamples {
    public static void main(String[] args) {
        // Example 1: Sorting primitive array (uses Dual-Pivot Quicksort)
        int[] numbers = {3, 1, 4, 1, 5, 9, 2, 6, 5, 3, 5};
        Arrays.sort(numbers);
        // numbers is now: [1, 1, 2, 3, 3, 4, 5, 5, 5, 6, 9]
        
        // Example 2: Sorting object array (uses Timsort - stable)
        String[] words = {"banana", "Apple", "cherry", "Date"};
        Arrays.sort(words);  // Lexicographic order (uppercase first)
        // ["Apple", "Date", "banana", "cherry"]
        
        // Example 3: Case-insensitive sorting
        Arrays.sort(words, String.CASE_INSENSITIVE_ORDER);
        // ["Apple", "banana", "cherry", "Date"]
        
        // Example 4: Sorting a range
        int[] data = {5, 3, 8, 4, 2, 7, 1, 9, 6};
        Arrays.sort(data, 2, 7);  // Sort indices 2-6 only
        // [5, 3, 1, 2, 4, 7, 8, 9, 6]
        //         ^^^^^^^^^^^^^ sorted portion
        
        // Example 5: Parallel sorting (for large arrays)
        int[] largeArray = new int[1_000_000];
        // ... fill with data ...
        Arrays.parallelSort(largeArray);  // Uses Fork/Join framework
        
        // Example 6: Sorting objects with custom comparator
        List<Person> people = new ArrayList<>();
        people.add(new Person("Alice", 30));
        people.add(new Person("Bob", 25));
        people.add(new Person("Charlie", 30));
        
        // Sort by age, then by name (stable sort preserves secondary order)
        people.sort(Comparator.comparingInt(Person::getAge)
                             .thenComparing(Person::getName));
        // Result: Bob(25), Alice(30), Charlie(30)
        
        // Example 7: Reverse order
        Arrays.sort(words, Comparator.reverseOrder());
        // Sorted in reverse lexicographic order
    }
}
 
class Person {
    private String name;
    private int age;
    
    Person(String name, int age) {
        this.name = name;
        this.age = age;
    }
    
    String getName() { return name; }
    int getAge() { return age; }
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59

// Example 1: Basic sorting (default is STRING comparison!)
const numbers = [3, 1, 4, 1, 5, 9, 2, 6, 5, 3, 5];
console.log([...numbers].sort());
// WRONG for numbers: [1, 1, 2, 3, 3, 4, 5, 5, 5, 6, 9] might be luck
// Actually would give: [1, 1, 2, 3, 3, 4, 5, 5, 5, 6, 9] for single digits
 
// but for larger numbers:
console.log([10, 2, 1].sort());
// Output: [1, 10, 2] - lexicographic string sorting!
 
// CORRECT: Always provide a compare function for numbers
console.log([10, 2, 1].sort((a, b) => a - b));
// Output: [1, 2, 10] - proper numeric sorting
 
// Example 2: Numeric sorting
const scores = [150, 28, 3000, 7, 99];
const ascending = [...scores].sort((a, b) => a - b);
const descending = [...scores].sort((a, b) => b - a);
console.log(ascending);  // [7, 28, 99, 150, 3000]
console.log(descending); // [3000, 150, 99, 28, 7]
 
// Example 3: String sorting
const fruits = ['banana', 'Apple', 'cherry', 'Date'];
console.log([...fruits].sort());
// ['Apple', 'Date', 'banana', 'cherry'] - uppercase first!
 
// Case-insensitive sorting
console.log([...fruits].sort((a, b) => 
    a.toLowerCase().localeCompare(b.toLowerCase())
));
// ['Apple', 'banana', 'cherry', 'Date']
 
// Example 4: Sorting objects
const products = [
    { name: 'Widget', price: 25 },
    { name: 'Gadget', price: 15 },
    { name: 'Doohickey', price: 25 },
    { name: 'Thingamajig', price: 10 }
];
 
// Sort by price
const byPrice = [...products].sort((a, b) => a.price - b.price);
console.log(byPrice.map(p => p.name));
// ['Thingamajig', 'Gadget', 'Widget', 'Doohickey']
 
// Sort by price, then by name (stable sort enables this!)
const byPriceThenName = [...products].sort((a, b) => {
    if (a.price !== b.price) return a.price - b.price;
    return a.name.localeCompare(b.name);
});
console.log(byPriceThenName.map(p => p.name));
// ['Thingamajig', 'Gadget', 'Doohickey', 'Widget']
// Note: Doohickey before Widget because D < W alphabetically
 
// Example 5: Sorting with toSorted() (ES2023 - non-mutating)
const original = [3, 1, 4, 1, 5];
const sorted = original.toSorted((a, b) => a - b);
console.log(original); // [3, 1, 4, 1, 5] - unchanged
console.log(sorted);   // [1, 1, 3, 4, 5] - new sorted array

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70

package main
 
import (
    "fmt"
    "sort"
    "strings"
)
 
func main() {
    // Example 1: Sorting a slice of integers
    numbers := []int{3, 1, 4, 1, 5, 9, 2, 6, 5, 3, 5}
    sort.Ints(numbers)
    fmt.Println(numbers) // [1 1 2 3 3 4 5 5 5 6 9]
    
    // Example 2: Sorting strings
    words := []string{"banana", "Apple", "cherry", "Date"}
    sort.Strings(words)
    fmt.Println(words) // [Apple Date banana cherry] (uppercase first)
    
    // Example 3: Sorting floats
    floats := []float64{3.14, 2.71, 1.41, 1.73}
    sort.Float64s(floats)
    fmt.Println(floats) // [1.41 1.73 2.71 3.14]
    
    // Example 4: Custom sorting with sort.Slice
    type Person struct {
        Name string
        Age  int
    }
    
    people := []Person{
        {"Alice", 30},
        {"Bob", 25},
        {"Charlie", 30},
        {"David", 20},
    }
    
    // Sort by age
    sort.Slice(people, func(i, j int) bool {
        return people[i].Age < people[j].Age
    })
    fmt.Println(people) // [David, Bob, Alice, Charlie]
    
    // Example 5: Stable sorting (preserves original order of equal elements)
    sort.SliceStable(people, func(i, j int) bool {
        return people[i].Age < people[j].Age
    })
    // If Alice was before Charlie originally, she stays before
    
    // Example 6: Reverse sorting
    sort.Sort(sort.Reverse(sort.IntSlice(numbers)))
    fmt.Println(numbers) // [9 6 5 5 5 4 3 3 2 1 1]
    
    // Example 7: Check if already sorted
    sorted := []int{1, 2, 3, 4, 5}
    fmt.Println(sort.IntsAreSorted(sorted)) // true
    
    // Example 8: Binary search on sorted slice
    sortedNums := []int{1, 3, 5, 7, 9, 11, 13, 15}
    index := sort.SearchInts(sortedNums, 7)
    fmt.Printf("Found 7 at index %d
", index) // Found 7 at index 3
    
    // Example 9: Case-insensitive string sort
    words2 := []string{"banana", "Apple", "cherry", "Date"}
    sort.Slice(words2, func(i, j int) bool {
        return strings.ToLower(words2[i]) < strings.ToLower(words2[j])
    })
    fmt.Println(words2) // [Apple banana cherry Date]
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76

fn main() {
    // Example 1: Basic sorting (stable by default)
    let mut numbers = vec![3, 1, 4, 1, 5, 9, 2, 6, 5, 3, 5];
    numbers.sort();  // Stable sort
    println!("{:?}", numbers);  // [1, 1, 2, 3, 3, 4, 5, 5, 5, 6, 9]
    
    // Example 2: Unstable sort (faster, less memory)
    let mut nums = vec![3, 1, 4, 1, 5, 9, 2, 6];
    nums.sort_unstable();
    println!("{:?}", nums);  // [1, 1, 2, 3, 4, 5, 6, 9]
    
    // Example 3: Reverse sorting
    let mut desc = vec![3, 1, 4, 1, 5];
    desc.sort();
    desc.reverse();  // In-place reversal
    println!("{:?}", desc);  // [5, 4, 3, 1, 1]
    
    // Or using sort_by with reversed comparator
    let mut desc2 = vec![3, 1, 4, 1, 5];
    desc2.sort_by(|a, b| b.cmp(a));  // Reverse comparison
    println!("{:?}", desc2);  // [5, 4, 3, 1, 1]
    
    // Example 4: Sorting by key
    let mut words = vec!["Banana", "apple", "Cherry", "date"];
    words.sort_by_key(|s| s.to_lowercase());
    println!("{:?}", words);  // ["apple", "Banana", "Cherry", "date"]
    
    // Example 5: Sorting structs
    #[derive(Debug)]
    struct Person {
        name: String,
        age: u32,
    }
    
    let mut people = vec![
        Person { name: "Alice".into(), age: 30 },
        Person { name: "Bob".into(), age: 25 },
        Person { name: "Charlie".into(), age: 30 },
    ];
    
    // Sort by age (stable, so Alice stays before Charlie)
    people.sort_by_key(|p| p.age);
    for p in &people {
        println!("{}: {}", p.name, p.age);
    }
    // Bob: 25, Alice: 30, Charlie: 30
    
    // Example 6: Complex multi-field sorting
    people.sort_by(|a, b| {
        match a.age.cmp(&b.age) {
            std::cmp::Ordering::Equal => a.name.cmp(&b.name),
            other => other,
        }
    });
    
    // Example 7: Check if sorted
    let sorted = vec![1, 2, 3, 4, 5];
    assert!(sorted.is_sorted());
    
    // Example 8: Partial sorting (unstable)
    let mut data = vec![5, 3, 8, 4, 2, 7, 1, 9, 6];
    data.select_nth_unstable(3);  // Put 4th smallest element in position 3
    // Elements before index 3 are <= element at index 3
    // Elements after index 3 are >= element at index 3
    
    // Example 9: Sorting with errors (sort_by returns Result)
    let mut items = vec![Some(5), None, Some(2), Some(7)];
    items.sort_by(|a, b| {
        match (a, b) {
            (Some(x), Some(y)) => x.cmp(y),
            (Some(_), None) => std::cmp::Ordering::Less,
            (None, Some(_)) => std::cmp::Ordering::Greater,
            (None, None) => std::cmp::Ordering::Equal,
        }
    });
}