Sorting in Practice - Learning Module

Loading content...

0/276

Built-in Sort Functions

From Theory to Practice: The Library-First Approach

Throughout this chapter, we've explored the theoretical foundations of sorting algorithms—from the elegant simplicity of Bubble Sort to the sophisticated efficiency of Quick Sort and Merge Sort, from comparison-based paradigms to the linear-time magic of Counting and Radix Sort. You now understand why these algorithms work, how they achieve their complexity bounds, and when each approach excels.

But here's a crucial insight that separates textbook knowledge from professional engineering: in production code, you almost never implement these algorithms yourself.

Every major programming language provides highly optimized, battle-tested sorting functions that represent thousands of hours of engineering effort, edge case handling, and performance tuning. These library implementations typically outperform hand-written code by significant margins while providing correctness guarantees that would take substantial effort to replicate.

What You Will Learn

By the end of this page, you will understand the built-in sorting mechanisms across major programming languages, their underlying algorithms, performance characteristics, memory behavior, and proper usage patterns. You'll know exactly what happens beneath the surface when you call sort(), enabling informed decisions in production code.

Why study sorting algorithms if libraries do the work?

This is a valid question, and the answer reinforces everything we've covered:

Understanding enables selection — Knowing the underlying algorithms helps you choose between different library functions (e.g., stable vs. unstable sort)
Debugging requires insight — When sorting behaves unexpectedly, algorithmic knowledge helps diagnose issues
Custom requirements demand adaptation — Some problems require sorting variants that libraries don't directly support
Interviews test fundamentals — Technical interviews assess your algorithmic thinking, not your ability to call library functions
Edge cases need understanding — Libraries have specific behaviors for edge cases that documentation may not fully explain

The Landscape of Library Sorting

Modern programming languages have converged on sophisticated hybrid algorithms for their standard sorting functions. Rather than implementing a single textbook algorithm, these libraries combine multiple techniques to achieve optimal performance across diverse input distributions.

Let's survey the major implementations and understand what powers them beneath the surface.

Built-in Sort Functions Across Major Languages
Language	Function	Algorithm	Worst Case	Stable
Python	list.sort() / sorted()	Timsort	O(n log n)	Yes ✓
JavaScript	Array.prototype.sort()	Timsort / Merge Sort*	O(n log n)	Yes** (ES2019+)
Java	Arrays.sort() (primitives)	Dual-Pivot Quicksort	O(n²)†	No
Java	Arrays.sort() (objects)	Timsort	O(n log n)	Yes ✓
C++	std::sort()	Introsort	O(n log n)	No
C++	std::stable_sort()	Merge Sort	O(n log n)	Yes ✓
Go	sort.Sort()	Pattern-defeating Quicksort	O(n log n)	No
Go	sort.Stable()	Block Sort	O(n log n)	Yes ✓
Rust	slice.sort()	Timsort variant	O(n log n)	Yes ✓
Rust	slice.sort_unstable()	Pattern-defeating Quicksort	O(n log n)	No

Notes on the table:

*JavaScript: V8 (Chrome/Node.js) switched from Quicksort to Timsort in 2018. SpiderMonkey (Firefox) uses Merge Sort. Implementation varies by engine.

**Stability: ECMAScript 2019 mandates that Array.prototype.sort() be stable. Prior versions allowed unstable implementations.

†O(n²): Dual-Pivot Quicksort has O(n²) worst case, but extensive techniques prevent this in practice (random pivot selection, switching to Heap Sort for pathological inputs).

The Hybrid Revolution

Notice that no mainstream language uses a single "pure" algorithm. Timsort combines Merge Sort and Insertion Sort. Introsort blends Quicksort, Heapsort, and Insertion Sort. This hybridization reflects decades of empirical research showing that real-world data has patterns pure algorithms don't exploit optimally.

Timsort — The Industry Standard

Timsort, developed by Tim Peters for Python in 2002, has become the de facto standard for library sorting. Its adoption by Java (for objects), Android, Swift, Rust, and V8 (JavaScript) demonstrates its exceptional real-world performance.

The core insight behind Timsort:

Real-world data is rarely random. It often contains pre-sorted subsequences (called runs) due to the nature of data generation—timestamps are naturally ordered, alphabetical lists maintain partial order, even randomly-generated data exhibits local patterns.

Timsort exploits this observation by:

Identifying natural runs — Finding existing ascending or descending sequences in the input
Extending short runs — Using Insertion Sort (optimal for small/nearly-sorted data) to ensure minimum run lengths
Merging intelligently — Using a sophisticated merge strategy that maintains balance while minimizing comparisons

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']

Timsort's Performance Characteristics:

Scenario	Time Complexity	Why
Random data	O(n log n)	Standard merge-based performance
Already sorted	O(n)	Single run detected, no merges needed
Reverse sorted	O(n)	Single descending run reversed, then treated as sorted
Many duplicates	O(n log n)	But fewer comparisons due to efficient merging
Partially sorted	O(n log k)	Where k is the number of runs; far better than O(n log n)

Timsort's Adaptive Advantage

The key performance insight: Timsort is adaptive. Its O(n log n) is worst-case for random data, but it often performs significantly better on structured data. In benchmarks on realistic datasets, Timsort can be 2-10x faster than pure Quicksort due to run exploitation.

Memory Usage:

Timsort requires O(n) auxiliary space in the worst case for merging. However, its implementation minimizes memory usage through:

In-place run identification — No extra memory needed to find runs
Lazy allocation — Merge buffer allocated only when needed
Galloping mode — Reduces comparisons during merges when one run "dominates"
Fixed-size merge buffer — Smaller of the two runs is copied, not both

For languages where memory matters (embedded systems, high-frequency trading), the O(n) space might prompt consideration of in-place alternatives.

Introsort — C++'s Pragmatic Hybrid

C++'s std::sort() uses Introsort (introspective sort), a hybrid algorithm developed by David Musser in 1997. Introsort addresses Quicksort's Achilles heel—its O(n²) worst case—while preserving its excellent average-case performance and cache efficiency.

The Introsort Strategy:

Start with Quicksort — Begin sorting with Quicksort, which has excellent cache locality and low overhead
Monitor recursion depth — Track how deep the recursive calls go
Switch to Heapsort — If depth exceeds 2 × log₂(n), switch to Heapsort for guaranteed O(n log n)
Finish with Insertion Sort — For small subarrays (typically ≤ 16 elements), use Insertion Sort

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;
}

Why C++ Uses Introsort Instead of Timsort:

In-place guarantee — std::sort is specified as O(1) auxiliary space on average. Timsort requires O(n) space.
Cache efficiency — Quicksort's in-place partitioning is more cache-friendly than Timsort's merging
Worst-case protection — The Heapsort fallback ensures O(n log n) even for pathological inputs
Historical context — Introsort was standardized before Timsort's mainstream adoption

Important Distinction: std::sort is not stable. Equal elements may be reordered. When stability matters, use std::stable_sort(), which uses a Merge Sort variant with O(n log² n) time if memory is limited.

C++ Iterator Requirements

std::sort requires RandomAccessIterators. This means you can use it with std::vector, std::array, std::deque, and raw pointers, but NOT with std::list or std::forward_list. For linked lists, use the container's member function: list.sort().

Java's Dual-Pivot Quicksort

Java takes an interesting approach: it uses different algorithms for primitives versus objects.

For primitive arrays (int[], long[], double[], etc.), Java uses Dual-Pivot Quicksort, developed by Vladimir Yaroslavskiy in 2009. This algorithm uses two pivots to create three partitions, reducing the average number of comparisons.

For object arrays (Object[], String[], etc.), Java uses Timsort, prioritizing stability since objects often carry additional semantics where order preservation matters.

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; }
}

Why the Primitive vs Object Distinction?

Criterion	Primitives	Objects
Stability needed	Rarely (primitives have no identity)	Often (objects have state beyond value)
Comparison cost	Very cheap (single CPU instruction)	Potentially expensive (equals/compareTo calls)
Memory patterns	Contiguous, cache-friendly	Objects scattered in heap
Optimal choice	Quicksort (fast, cache-efficient)	Timsort (fewer comparisons, stable)

Dual-Pivot Quicksort Insight:

Traditional Quicksort uses one pivot, creating two partitions. Dual-Pivot Quicksort uses two pivots (P1 < P2), creating three partitions:

Elements < P1
Elements between P1 and P2
Elements > P2

This seemingly minor change reduces the average number of comparisons from ~2n ln(n) to ~1.9n ln(n)—a measurable improvement at scale.

Arrays.parallelSort() for Large Data

For arrays with more than ~8,192 elements, consider Arrays.parallelSort(). It splits the array and uses multiple threads via the Fork/Join framework. On multi-core systems, it can achieve near-linear speedup. However, the parallelization overhead makes it slower for small arrays.

JavaScript's Engine-Dependent Sorting

JavaScript's Array.prototype.sort() has a unique history in the sorting landscape. The ECMAScript specification historically said almost nothing about the algorithm, only requiring that it be a comparison sort. This led to different engines implementing vastly different algorithms.

Historical Implementation Variance:

V8 (Chrome/Node.js): Used Quicksort until 2018, then switched to Timsort
SpiderMonkey (Firefox): Uses Merge Sort
JavaScriptCore (Safari): Has varied between Bucket Sort and Timsort

The ES2019 Stability Mandate:

Before ECMAScript 2019, sort() was allowed to be unstable. This led to subtle bugs when developers expected equal elements to retain their original order. ES2019 mandated stability, prompting V8's switch from Quicksort to Timsort.

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

Critical: JavaScript's Default String Comparison

JavaScript's sort() without a compare function converts elements to strings and compares Unicode code points. This means [10, 2, 1].sort() returns [1, 10, 2], not [1, 2, 10]. ALWAYS provide a compare function for numeric sorting. This is the #1 JavaScript sorting pitfall.

The Compare Function Contract:

JavaScript's compare function must follow these rules:

compareFunction(a, b):
  - Returns negative value → a comes before b
  - Returns positive value → b comes before a  
  - Returns zero → a and b are equal (maintain original order if stable)

Common Patterns:

Use Case	Compare Function
Numbers ascending	`(a, b) => a - b`
Numbers descending	`(a, b) => b - a`
Strings ascending	`(a, b) => a.localeCompare(b)`
Strings descending	`(a, b) => b.localeCompare(a)`
By object property	`(a, b) => a.property - b.property`
Boolean true first	`(a, b) => (b.flag === true) - (a.flag === true)`

Go's Pattern-Defeating Quicksort

Go's sort package uses Pattern-Defeating Quicksort (pdqsort), a cutting-edge algorithm developed by Orson Peters that represents the state of the art in unstable sorting. Pdqsort achieves best-case, average-case, and worst-case O(n log n) while matching or exceeding traditional Quicksort's average-case performance.

How pdqsort Works:

Start like Quicksort — Use partitioning as the primary strategy
Detect patterns — Identify pre-sorted runs, lots of duplicates, or pathological pivot choices
Adapt to input — Switch strategies based on what's detected:
- For random data: Pure Quicksort (fastest)
- For mostly sorted: Insertion Sort
- For lots of duplicates: Three-way partitioning
- For bad pivot sequences: Fallback to guaranteed O(n log n)

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
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\n", 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]
}

sort.Slice vs Implementing sort.Interface

Go offers two approaches: sort.Slice (convenient, uses a closure) or implementing the sort.Interface (Len, Less, Swap methods). For simple cases, use sort.Slice. For frequently-sorted types, implementing the interface may be cleaner and avoids closure allocation overhead.

Go's Stable Sort:

For stable sorting, Go provides sort.SliceStable() and sort.Stable(). These use a block sort algorithm (also known as "block merge sort" or "wiki sort") that achieves O(n log n) time while being stable and requiring only O(1) extra space. This is a significant engineering achievement—most stable sorts require O(n) space.

Performance Considerations:

Function	Algorithm	Stable	Space	Best For
`sort.Ints()`	pdqsort	No	O(1)	General-purpose integer sorting
`sort.Slice()`	pdqsort	No	O(1)	Custom comparisons
`sort.SliceStable()`	Block sort	Yes	O(1)	When order of equals matters

Rust's Careful Design

Rust's standard library demonstrates thoughtful API design by explicitly offering both stable and unstable sorting, with clear naming that signals the tradeoff.

slice.sort() — Stable sort using a Timsort variant; O(n log n) time, O(n) space
slice.sort_unstable() — Unstable sort using pdqsort; O(n log n) time, O(log n) space

The naming is intentional: sort() is the "safe default" (stable), while sort_unstable() requires explicit acknowledgment that stability isn't guaranteed.

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,
        }
    });
}

Rust's Safety Guarantees

Rust's sort functions require Ord trait for sort() and PartialOrd for sort_by. This compile-time enforcement prevents runtime errors from incomparable types. If your comparison can fail (like with NaN floats), you must handle it explicitly in sort_by().

When to Use Each Sort:

Scenario	Recommended Function	Reason
Default choice	`sort()`	Stable, correct behavior guaranteed
Performance-critical, no duplicates	`sort_unstable()`	Faster, less memory
Expensive clone/copy types	`sort_unstable()`	Fewer element movements
Preserving secondary order	`sort()`	Stability ensures consistent results
Partial sorting needs	`select_nth_unstable()`	O(n) average for kth element

Memory Comparison:

Function	Space Complexity	Notes
`sort()`	O(n)	Timsort merge buffer
`sort_unstable()`	O(log n)	Stack space only
`sort_by()` / `sort_by_key()`	Same as sort()	Stable variants

Summary: Choosing and Using Library Sorts

We've surveyed the sorting landscape across major programming languages. Let's consolidate this knowledge into practical guidance:

Key Takeaways

•Library sorts are sophisticated hybrids — Timsort, Introsort, and pdqsort combine multiple algorithms to handle real-world data better than any single textbook algorithm.
•Stability has concrete meaning — Stable sorts preserve original order of equal elements. This matters for multi-field sorting and user expectations.
•Algorithm choice varies by language — Python and Java (objects) use Timsort; C++ uses Introsort; Go and Rust offer pdqsort for unstable sorts.
•Default behaviors differ critically — JavaScript's default string comparison is a common pitfall. Always provide compare functions for numeric data.
•Space-time tradeoffs exist in library choices — Stable sorts typically need O(n) space; unstable sorts can be O(log n) or O(1).
•Parallel sorting is available for large data — Java's parallelSort(), Python's multiprocessing-based approaches, and language-specific parallel libraries.

Quick Reference: Default Sort Behavior
Language	Numeric Default	String Default	Stable Default
Python	Numeric order ✓	Lexicographic ✓	Yes ✓
JavaScript	⚠️ String order!	Lexicographic ✓	Yes (ES2019+)
Java (primitives)	Numeric order ✓	N/A	No
Java (objects)	Per compareTo ✓	Lexicographic ✓	Yes ✓
C++ std::sort	Numeric order ✓	Lexicographic ✓	No
Go	Numeric order ✓	Lexicographic ✓	No
Rust	Numeric order ✓	Lexicographic ✓	Yes ✓

Page Complete

You now understand the built-in sorting mechanisms across major programming languages. You know what algorithms power them, their stability guarantees, and their performance characteristics. In the next page, we'll explore how to customize these library sorts through comparison functions and custom ordering.