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
28
29
30
31
32

// Consider these objects that will be compared by 'category' only
const items = [
    { id: 1, name: "Widget A", category: "tools" },
    { id: 2, name: "Widget B", category: "parts" },
    { id: 3, name: "Widget C", category: "tools" },  // Same category as id:1
    { id: 4, name: "Widget D", category: "parts" },  // Same category as id:2
    { id: 5, name: "Widget E", category: "tools" },  // Same category as id:1,3
];
 
// Original order: 1, 2, 3, 4, 5
 
// When sorting by category...
 
// STABLE SORT OUTPUT:
// [
//   { id: 2, category: "parts" },  // First "parts" in original
//   { id: 4, category: "parts" },  // Second "parts" in original
//   { id: 1, category: "tools" },  // First "tools" in original
//   { id: 3, category: "tools" },  // Second "tools" in original
//   { id: 5, category: "tools" },  // Third "tools" in original
// ]
// Within each category, original order (2,4) and (1,3,5) is preserved!
 
// UNSTABLE SORT OUTPUT (one possible result):
// [
//   { id: 4, category: "parts" },  // Order within "parts" is arbitrary
//   { id: 2, category: "parts" },
//   { id: 5, category: "tools" },  // Order within "tools" is arbitrary
//   { id: 1, category: "tools" },
//   { id: 3, category: "tools" },
// ]
// Elements are correctly grouped by category, but order within groups varies

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

# Example: Sort employees by department, then by seniority, then by name
employees = [
    {"name": "Alice", "dept": "Engineering", "years": 5},
    {"name": "Bob", "dept": "Sales", "years": 3},
    {"name": "Carol", "dept": "Engineering", "years": 5},
    {"name": "David", "dept": "Sales", "years": 7},
    {"name": "Eve", "dept": "Engineering", "years": 3},
    {"name": "Frank", "dept": "Sales", "years": 3},
]
 
# Multi-sort approach: sort by least significant first, most significant last
# Python's sort is STABLE, so this works!
 
# Step 1: Sort by name (least significant)
employees.sort(key=lambda x: x["name"])
# [Alice, Bob, Carol, David, Eve, Frank]
 
# Step 2: Sort by years (middle significance)
employees.sort(key=lambda x: x["years"])
# [Bob(3), Eve(3), Frank(3), Alice(5), Carol(5), David(7)]
# Notice: Bob, Eve, Frank all have 3 years - their alphabetical order is preserved!
 
# Step 3: Sort by department (most significant)
employees.sort(key=lambda x: x["dept"])
# Engineering: Eve(3), Alice(5), Carol(5) — sorted by years, then name within years
# Sales: Bob(3), Frank(3), David(7) — sorted by years, then name within years
 
# Final result:
# [Eve, Alice, Carol, Bob, Frank, David]
 
# This is equivalent to a single sort with a tuple key:
employees_alt = sorted(employees, key=lambda x: (x["dept"], x["years"], x["name"]))
# Same result, but the multi-sort approach is sometimes cleaner for dynamic criteria
 
 
# === WHY UNSTABLE SORT BREAKS THIS ===
 
# If the sort in Step 2 were unstable, employees with equal years
# might NOT preserve their alphabetical order from Step 1.
# Bob, Eve, Frank could become Frank, Bob, Eve — losing the name 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
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
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95

#include <algorithm>
#include <vector>
#include <numeric>  // for std::iota
#include <iostream>
 
struct Item {
    std::string name;
    int category;
};
 
int main() {
    std::vector<Item> items = {
        {"Alpha", 2},
        {"Beta", 1},
        {"Gamma", 2},
        {"Delta", 1},
        {"Epsilon", 2}
    };
    
    // Original order: Alpha, Beta, Gamma, Delta, Epsilon
    // Want to sort by category while preserving order within each category
    
    // METHOD 1: Use std::stable_sort directly
    std::stable_sort(items.begin(), items.end(),
        [](const Item& a, const Item& b) {
            return a.category < b.category;
        });
    // Result: Beta(1), Delta(1), Alpha(2), Gamma(2), Epsilon(2)
    // Correct! Original order preserved within categories.
    
    
    // METHOD 2: Index trick with std::sort (when stable_sort isn't an option)
    std::vector<Item> items2 = {
        {"Alpha", 2},
        {"Beta", 1},
        {"Gamma", 2},
        {"Delta", 1},
        {"Epsilon", 2}
    };
    
    // Create index array [0, 1, 2, 3, 4]
    std::vector<size_t> indices(items2.size());
    std::iota(indices.begin(), indices.end(), 0);  // Fill with 0, 1, 2, ...
    
    // Sort indices using category as primary key, original index as tie-breaker
    std::sort(indices.begin(), indices.end(),
        [&items2](size_t i, size_t j) {
            if (items2[i].category != items2[j].category) {
                return items2[i].category < items2[j].category;
            }
            return i < j;  // Tie-breaker: preserve original order
        });
    // indices is now [1, 3, 0, 2, 4]
    //                 Beta, Delta, Alpha, Gamma, Epsilon
    
    // Reorder items according to sorted indices
    std::vector<Item> sorted_items;
    for (size_t idx : indices) {
        sorted_items.push_back(items2[idx]);
    }
    // sorted_items: Beta(1), Delta(1), Alpha(2), Gamma(2), Epsilon(2)
    // Stable sorting achieved with unstable std::sort!
    
    
    // METHOD 3: Pair items with their indices
    std::vector<Item> items3 = {
        {"Alpha", 2},
        {"Beta", 1},
        {"Gamma", 2},
        {"Delta", 1},
        {"Epsilon", 2}
    };
    
    std::vector<std::pair<Item, size_t>> indexed_items;
    for (size_t i = 0; i < items3.size(); ++i) {
        indexed_items.emplace_back(items3[i], i);
    }
    
    std::sort(indexed_items.begin(), indexed_items.end(),
        [](const auto& a, const auto& b) {
            if (a.first.category != b.first.category) {
                return a.first.category < b.first.category;
            }
            return a.second < b.second;  // Use original index as tie-breaker
        });
    
    // Extract sorted items
    std::vector<Item> result;
    for (const auto& [item, idx] : indexed_items) {
        result.push_back(item);
    }
    // result: Beta(1), Delta(1), Alpha(2), Gamma(2), Epsilon(2)
    
    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
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82

package main
 
import (
    "fmt"
    "sort"
)
 
type Item struct {
    Name     string
    Category int
    Index    int  // We'll use this to track original position
}
 
func main() {
    items := []Item{
        {"Alpha", 2, 0},
        {"Beta", 1, 1},
        {"Gamma", 2, 2},
        {"Delta", 1, 3},
        {"Epsilon", 2, 4},
    }
    
    // METHOD 1: Use sort.SliceStable (the easy way)
    sort.SliceStable(items, func(i, j int) bool {
        return items[i].Category < items[j].Category
    })
    // Result: Beta(1), Delta(1), Alpha(2), Gamma(2), Epsilon(2)
    
    
    // METHOD 2: Simulate stability with sort.Slice using Index field
    items2 := []Item{
        {"Alpha", 2, 0},
        {"Beta", 1, 1},
        {"Gamma", 2, 2},
        {"Delta", 1, 3},
        {"Epsilon", 2, 4},
    }
    
    // Include original index in comparison for tie-breaking
    sort.Slice(items2, func(i, j int) bool {
        if items2[i].Category != items2[j].Category {
            return items2[i].Category < items2[j].Category
        }
        return items2[i].Index < items2[j].Index  // Preserve original order
    })
    // Result: Beta(1), Delta(1), Alpha(2), Gamma(2), Epsilon(2)
    
    
    // METHOD 3: Without modifying struct (index wrapper)
    type IndexedItem struct {
        Item  Item
        Index int
    }
    
    rawItems := []Item{
        {"Alpha", 2, 0},
        {"Beta", 1, 0},
        {"Gamma", 2, 0},
        {"Delta", 1, 0},
        {"Epsilon", 2, 0},
    }
    
    indexed := make([]IndexedItem, len(rawItems))
    for i, item := range rawItems {
        indexed[i] = IndexedItem{item, i}
    }
    
    sort.Slice(indexed, func(i, j int) bool {
        if indexed[i].Item.Category != indexed[j].Item.Category {
            return indexed[i].Item.Category < indexed[j].Item.Category
        }
        return indexed[i].Index < indexed[j].Index
    })
    
    result := make([]Item, len(indexed))
    for i, idx := range indexed {
        result[i] = idx.Item
    }
    // result: Beta(1), Delta(1), Alpha(2), Gamma(2), Epsilon(2)
    
    fmt.Println(result)
}

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

use std::time::Instant;
 
fn main() {
    let n = 1_000_000;
    
    // Generate random data
    let mut data1: Vec<i32> = (0..n).map(|_| rand::random()).collect();
    let mut data2 = data1.clone();
    
    // Benchmark stable sort
    let start = Instant::now();
    data1.sort();  // Stable (Timsort variant)
    let stable_time = start.elapsed();
    
    // Benchmark unstable sort
    let start = Instant::now();
    data2.sort_unstable();  // Unstable (pdqsort)
    let unstable_time = start.elapsed();
    
    println!("Stable sort:   {:?}", stable_time);
    println!("Unstable sort: {:?}", unstable_time);
    println!("Speedup: {:.2}x", stable_time.as_secs_f64() / unstable_time.as_secs_f64());
    
    // Typical results on random data:
    // Stable sort:   ~150ms
    // Unstable sort: ~80ms
    // Speedup: ~1.8x
    
    // ===== LARGE OBJECTS TEST =====
    
    #[derive(Clone)]
    struct LargeItem {
        key: i32,
        data: [u8; 1024],  // 1KB padding
    }
    
    let mut large1: Vec<LargeItem> = (0..100_000)
        .map(|i| LargeItem { key: rand::random(), data: [0; 1024] })
        .collect();
    let mut large2 = large1.clone();
    
    let start = Instant::now();
    large1.sort_by_key(|x| x.key);  // Stable
    let stable_large = start.elapsed();
    
    let start = Instant::now();
    large2.sort_unstable_by_key(|x| x.key);  // Unstable
    let unstable_large = start.elapsed();
    
    println!("
Large objects:");
    println!("Stable sort:   {:?}", stable_large);
    println!("Unstable sort: {:?}", unstable_large);
    println!("Speedup: {:.2}x", stable_large.as_secs_f64() / unstable_large.as_secs_f64());
    
    // With large objects, the unstable sort advantage increases
    // because it moves elements fewer times.
    // Typical speedup: 2-4x for 1KB objects
}

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
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137

/**
 * Tests whether a sort function is stable.
 * @param sortFn - The sort function to test (mutates array in place)
 * @param compareFn - The comparison function used by the sort
 * @returns boolean - true if the sort is stable
 */
function testSortStability(sortFn, compareFn) {
    // Create test data with deliberate duplicates
    const testCases = [
        // Case 1: All equal elements
        [
            { key: 1, id: 'a' },
            { key: 1, id: 'b' },
            { key: 1, id: 'c' },
            { key: 1, id: 'd' },
        ],
        
        // Case 2: Groups of duplicates
        [
            { key: 2, id: 'a' },
            { key: 1, id: 'b' },
            { key: 2, id: 'c' },
            { key: 1, id: 'd' },
            { key: 2, id: 'e' },
        ],
        
        // Case 3: Duplicates at edges
        [
            { key: 1, id: 'a' },
            { key: 1, id: 'b' },
            { key: 2, id: 'c' },
            { key: 3, id: 'd' },
            { key: 3, id: 'e' },
        ],
        
        // Case 4: Large number of duplicates
        Array.from({ length: 100 }, (_, i) => ({
            key: i % 5,  // Only 5 distinct keys
            id: String(i).padStart(3, '0'),
        })),
    ];
    
    for (const original of testCases) {
        // Clone the array
        const toSort = original.map(item => ({ ...item }));
        
        // Record original indices for each unique id
        const originalOrder = new Map();
        original.forEach((item, idx) => {
            originalOrder.set(item.id, idx);
        });
        
        // Sort using the provided function
        sortFn(toSort, compareFn);
        
        // Verify stability: for items with equal keys, check if relative order preserved
        for (let i = 0; i < toSort.length - 1; i++) {
            const current = toSort[i];
            const next = toSort[i + 1];
            
            // If keys are equal, check that original order is preserved
            if (compareFn(current, next) === 0) {
                const originalIdxCurrent = originalOrder.get(current.id);
                const originalIdxNext = originalOrder.get(next.id);
                
                if (originalIdxCurrent > originalIdxNext) {
                    console.log(`Stability violation: ${current.id} (orig: ${originalIdxCurrent}) came before ${next.id} (orig: ${originalIdxNext})`);
                    return false;
                }
            }
        }
    }
    
    return true;
}
 
// Test JavaScript's built-in sort (should be stable in ES2019+)
const jsSort = (arr, cmp) => arr.sort(cmp);
const compareByKey = (a, b) => a.key - b.key;
 
console.log('JavaScript sort is stable:', testSortStability(jsSort, compareByKey));
 
 
/**
 * Visualization helper: shows the sort result with stability indication
 */
function visualizeSortStability(items, compareFn) {
    console.log('\nOriginal order:');
    items.forEach((item, idx) => {
        console.log(`  [${idx}] key=${item.key}, id=${item.id}`);
    });
    
    const sorted = [...items].sort(compareFn);
    
    console.log('\nSorted order:');
    sorted.forEach((item, idx) => {
        const originalIdx = items.findIndex(o => o.id === item.id);
        console.log(`  [${idx}] key=${item.key}, id=${item.id} (was at ${originalIdx})`);
    });
    
    // Check and report on stability
    console.log('\nStability analysis:');
    const groups = new Map();
    sorted.forEach((item, sortedIdx) => {
        if (!groups.has(item.key)) {
            groups.set(item.key, []);
        }
        groups.get(item.key).push({
            id: item.id,
            originalIdx: items.findIndex(o => o.id === item.id),
            sortedIdx,
        });
    });
    
    let isStable = true;
    for (const [key, group] of groups) {
        if (group.length > 1) {
            const originalOrder = group.map(g => g.originalIdx);
            const isGroupStable = originalOrder.every((v, i, a) => i === 0 || a[i-1] < v);
            console.log(`  Key ${key}: [${group.map(g => g.id).join(', ')}] - ${isGroupStable ? 'STABLE ✓' : 'UNSTABLE ✗'}`);
            if (!isGroupStable) isStable = false;
        }
    }
    
    console.log(`\nOverall: ${isStable ? 'Sort is STABLE' : 'Sort is UNSTABLE'}`);
}
 
// Example usage
const testData = [
    { key: 2, id: 'alpha' },
    { key: 1, id: 'beta' },
    { key: 2, id: 'gamma' },
    { key: 1, id: 'delta' },
    { key: 2, id: 'epsilon' },
];
 
visualizeSortStability(testData, (a, b) => a.key - b.key);

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
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149

"""
E-Commerce Product Ranking System
 
Requirements:
1. Products are ranked by a relevance score from search algorithm
2. Within same relevance score, show sponsored products first
3. Within same relevance and sponsorship, maintain original database order
 
Original database order matters because:
- Newer products should appear before older ones (recency bias)
- Editorial-curated products should keep their placement
- A/B testing may depend on consistent ordering
"""
 
from dataclasses import dataclass
from datetime import datetime
from typing import List
 
@dataclass
class Product:
    id: str
    name: str
    relevance_score: float
    is_sponsored: bool
    created_at: datetime
    
    def __repr__(self):
        sponsored = "📣" if self.is_sponsored else "  "
        return f"{sponsored} [{self.relevance_score:.1f}] {self.name}"
 
 
def get_mock_products() -> List[Product]:
    """Simulate database query returning products in creation order"""
    return [
        Product("P001", "Widget Pro", 0.95, False, datetime(2024, 1, 15)),
        Product("P002", "Budget Widget", 0.85, True, datetime(2024, 1, 10)),  # Sponsored
        Product("P003", "Widget Basic", 0.85, False, datetime(2024, 1, 12)),
        Product("P004", "Premium Widget", 0.95, True, datetime(2024, 1, 8)),   # Sponsored
        Product("P005", "Widget Lite", 0.85, False, datetime(2024, 1, 14)),
        Product("P006", "Widget Max", 0.95, False, datetime(2024, 1, 5)),
        Product("P007", "Widget Mini", 0.75, True, datetime(2024, 1, 1)),      # Sponsored
    ]
 
 
def rank_products_wrong(products: List[Product]) -> List[Product]:
    """
    WRONG APPROACH: Using unstable sort simulation
    (Python's sort is stable, so we'll simulate instability)
    """
    import random
    
    # Simulate unstable sort by adding random tie-breaking
    return sorted(products, key=lambda p: (
        -p.relevance_score,
        not p.is_sponsored,
        random.random()  # This simulates unstable behavior
    ))
 
 
def rank_products_correct(products: List[Product]) -> List[Product]:
    """
    CORRECT APPROACH: Using Python's stable sort with multi-pass
    
    Sort order (least significant first for multi-pass):
    1. Original order - maintained by stable sort (no explicit action)
    2. Sponsorship - sponsored first
    3. Relevance score - highest first
    """
    # Because Python's sort is stable, we can sort in reverse priority order
    working = list(products)  # Don't modify original
    
    # Step 1: Already in database order (original input)
    
    # Step 2: Sort by sponsorship (sponsored first = not is_sponsored ascending)
    # Stable sort preserves database order within same sponsorship status
    working.sort(key=lambda p: not p.is_sponsored)
    
    # Step 3: Sort by relevance (highest first = negative score ascending)  
    # Stable sort preserves (database order + sponsorship) within same relevance
    working.sort(key=lambda p: -p.relevance_score)
    
    return working
 
 
def rank_products_single_pass(products: List[Product]) -> List[Product]:
    """
    Alternative: Single pass with tuple key
    
    This achieves the same result in one sort by including original index
    """
    indexed = list(enumerate(products))
    
    indexed.sort(key=lambda item: (
        -item[1].relevance_score,    # Primary: highest relevance first
        not item[1].is_sponsored,    # Secondary: sponsored first (True < False when negated)
        item[0]                      # Tertiary: original database order
    ))
    
    return [product for _, product in indexed]
 
 
def demonstrate():
    products = get_mock_products()
    
    print("=" * 60)
    print("Original Database Order:")
    print("=" * 60)
    for i, p in enumerate(products):
        print(f"  {i+1}. {p}")
    
    print()
    print("=" * 60)
    print("Correct Ranking (Multi-Pass Stable Sort):")
    print("=" * 60)
    ranked = rank_products_correct(products)
    for i, p in enumerate(ranked):
        print(f"  {i+1}. {p}")
    
    # Verify the ranking
    print()
    print("Analysis:")
    print("-" * 60)
    
    # Group by relevance
    from itertools import groupby
    for score, group in groupby(ranked, key=lambda p: p.relevance_score):
        group_list = list(group)
        sponsored = [p for p in group_list if p.is_sponsored]
        non_sponsored = [p for p in group_list if not p.is_sponsored]
        
        print(f"\nRelevance {score}:")
        if sponsored:
            print(f"  Sponsored (first): {[p.name for p in sponsored]}")
        if non_sponsored:
            print(f"  Regular (after): {[p.name for p in non_sponsored]}")
 
 
if __name__ == "__main__":
    demonstrate()
    
    # Expected output:
    # Relevance 0.95:
    #   Sponsored (first): ['Premium Widget']  (P004)
    #   Regular (after): ['Widget Pro', 'Widget Max']  (P001, P006 - database order)
    # Relevance 0.85:
    #   Sponsored (first): ['Budget Widget']  (P002)
    #   Regular (after): ['Widget Basic', 'Widget Lite']  (P003, P005 - database order)
    # Relevance 0.75:
    #   Sponsored (first): ['Widget Mini']  (P007)