Data Structures & AlgorithmsSorting in Practice

Sorting in Practice — Library Functions

LevelIntermediate

Duration60 mins

TopicSorting in Practice

2 / 4

Customizing Comparison Functions

Beyond Default Ordering: The Power of Custom Comparisons

Library sort functions provide sensible defaults—numbers sort numerically, strings sort lexicographically. But real-world applications demand far more sophisticated ordering:

Sort users by activity date descending, then by name ascending
Order products with in-stock items first, then by price
Arrange files with directories before files, then alphabetically
Sort search results by relevance, with sponsored posts first
Order tasks by priority level, then by due date, with overdue items first

These requirements are where custom comparison functions (also called comparators, compare functions, or ordering predicates) become essential. They transform generic sort algorithms into precisely tailored ordering systems.

What You Will Learn

By the end of this page, you will master comparison function design across multiple languages. You'll understand the mathematical properties that make comparisons valid, avoid subtle bugs that break sort stability and correctness, and implement complex multi-criteria sorting with confidence.

The Comparison Function Contract

Every library sort function assumes your comparison function obeys specific mathematical rules. Violating these rules doesn't just produce wrong results—it can cause infinite loops, crashes, or unpredictable behavior.

The Three Essential Properties:

A valid comparison function must be a strict weak ordering, which requires three properties:

Mathematical Properties of Valid Comparisons

•Irreflexivity — An element is never "less than" itself: compare(a, a) must indicate equality (return 0, or return false for less-than predicates). No element comes before itself.
•Asymmetry — If a comes before b, then b cannot come before a: if compare(a, b) < 0, then compare(b, a) > 0. Ordering is one-way.
•Transitivity — If a comes before b, and b comes before c, then a must come before c: if compare(a, b) < 0 and compare(b, c) < 0, then compare(a, c) < 0. Ordering chains must be consistent.

A fourth property for equivalence:

Transitivity of Equivalence — If a is equivalent to b, and b is equivalent to c, then a must be equivalent to c. This ensures that "equal" elements form consistent groups.

Why These Rules Matter:

Sorting algorithms rely on these properties to make decisions about where to place elements. If compare(a, b) < 0 but compare(b, a) < 0 (violating asymmetry), the algorithm might endlessly swap them. If compare(a, b) < 0 and compare(b, c) < 0 but compare(a, c) >= 0 (violating transitivity), the final ordering is undefined.

The #1 Comparison Bug

The most common comparison bug is returning 0 (equal) for unequal elements when it shouldn't, or using non-deterministic comparisons (e.g., based on random values or mutable state). These violate transitivity and can cause subtle, intermittent bugs that are extremely hard to debug.

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
// ✅ VALID: Simple numeric comparison
const valid1 = (a, b) => a - b;  // Obeys all three properties
 
// ✅ VALID: String comparison
const valid2 = (a, b) => a.localeCompare(b);  // Built-in is correct
 
// ❌ INVALID: Non-transitive comparison
// This compares by the first digit only
const invalid1 = (a, b) => {
    const firstA = String(a)[0];
    const firstB = String(b)[0];
    return firstA.localeCompare(firstB);
};
// Problem: 19 and 12 are "equal" (both start with 1)
//          12 and 25 are "equal"? No, 1 < 2, so 12 < 25
//          But 19 and 25? 1 < 2, so 19 < 25
// This seems okay... let's try another example:
// 15, 19, 12 — by this logic 15=19=12 (all start with 1)
// But we could end up with [19, 12, 15] or any permutation
// Actually this breaks because it's not a strict ordering at all
 
// ❌ INVALID: Random comparison (non-deterministic)
const invalid2 = (a, b) => Math.random() - 0.5;  // DON'T DO THIS!
// Violates asymmetry: same pair might return different results on each call
 
// ❌ INVALID: Asymmetry violation
const invalid3 = (a, b) => a.priority - b.priority || -1;
// When priorities are equal, always returns -1 (a < b)
// But then compare(b, a) also returns -1 (b < a)!
// Violates asymmetry: both a < b and b < a can't be true
 
// ✅ VALID: Correct multi-field comparison
const valid3 = (a, b) => {
    if (a.priority !== b.priority) {
        return a.priority - b.priority;
    }
    return a.name.localeCompare(b.name);
};

Comparison Function Signatures by Language

Different languages use different conventions for comparison functions. Understanding these conventions is crucial for writing correct comparators.

Comparison Function Conventions Across Languages
Language	Signature	Return Values	Notes
Python	`key=func` or `cmp_to_key`	Key: any comparable value Cmp: -1, 0, +1	Modern Python prefers key functions; cmp_to_key for legacy
JavaScript	`(a, b) => number`	Negative: a first 0: equal Positive: b first	Return actual difference for numbers, not just -1/0/1
Java	`Comparator<T>` interface	-1, 0, +1 (by convention) Any negative/positive works	Use Comparator.comparing() for modern approach
C++	`bool(a, b)` predicate	true: a < b false: a >= b	Strict less-than semantics; NOT a three-way comparison
Go	`func(i, j int) bool`	true: element[i] < element[j] false: otherwise	Operates on indices, not values directly
Rust	`Fn(&T, &T) -> Ordering`	`Less`, `Equal`, `Greater`	Enum provides type safety; can also use key functions

C++'s Boolean Predicate Is Different

C++'s comparison function returns bool, not int. It answers "is a strictly less than b?" not "how does a compare to b?". Returning true when a equals b violates strict weak ordering and causes undefined behavior. Always use a < b, never a <= b.

Python's Key Functions

Python takes a unique approach among mainstream languages: instead of comparison functions, it primarily uses key functions. A key function transforms each element into a value that Python's default comparison can handle.

Why Key Functions?

Simpler to write — No need to think about -1/0/+1 semantics
Fewer bugs — Key functions can't violate strict weak ordering as easily
More efficient — Key is computed once per element, not once per comparison
Composable — Multiple keys can be combined with tuples

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
from functools import cmp_to_key
from operator import attrgetter, itemgetter
 
# Example 1: Sort strings by length
words = ["apple", "pie", "banana", "strawberry"]
sorted_by_length = sorted(words, key=len)
print(sorted_by_length)  # ['pie', 'apple', 'banana', 'strawberry']
 
# Example 2: Sort case-insensitively
words = ["Banana", "apple", "Cherry"]
sorted_case_insensitive = sorted(words, key=str.lower)
print(sorted_case_insensitive)  # ['apple', 'Banana', 'Cherry']
 
# Example 3: Sort by absolute value
numbers = [-5, 2, -1, 7, -3]
sorted_by_abs = sorted(numbers, key=abs)
print(sorted_by_abs)  # [-1, 2, -3, -5, 7]
 
# Example 4: Sort dictionaries by a specific key
products = [
    {"name": "Widget", "price": 25.99, "stock": 100},
    {"name": "Gadget", "price": 15.99, "stock": 50},
    {"name": "Doohickey", "price": 25.99, "stock": 75},
]
 
# By price
by_price = sorted(products, key=lambda x: x["price"])
print([p["name"] for p in by_price])  # ['Gadget', 'Widget', 'Doohickey']
 
# By price, then by stock (descending) — use tuples!
by_price_then_stock = sorted(products, key=lambda x: (x["price"], -x["stock"]))
print([p["name"] for p in by_price_then_stock])  # ['Gadget', 'Doohickey', 'Widget']
# Doohickey comes before Widget: same price, but 75 > 50 (negated comparison)
 
# Example 5: Sort objects by attribute
class Person:
    def __init__(self, name, age, salary):
        self.name = name
        self.age = age
        self.salary = salary
    def __repr__(self):
        return f"{self.name}({self.age})"
 
people = [
    Person("Alice", 30, 70000),
    Person("Bob", 25, 50000),
    Person("Charlie", 30, 60000),
]
 
# Using lambda
by_age = sorted(people, key=lambda p: p.age)
print(by_age)  # [Bob(25), Alice(30), Charlie(30)]
 
# Using attrgetter (faster for frequently-used sorts)
by_age_v2 = sorted(people, key=attrgetter("age"))
print(by_age_v2)  # [Bob(25), Alice(30), Charlie(30)]
 
# Multiple attributes
by_age_then_salary = sorted(people, key=attrgetter("age", "salary"))
print(by_age_then_salary)  # [Bob(25), Charlie(30), Alice(30)]
# Charlie before Alice: same age, but 60000 < 70000
 
# Example 6: Descending order
by_age_desc = sorted(people, key=lambda p: p.age, reverse=True)
print(by_age_desc)  # [Alice(30), Charlie(30), Bob(25)]
 
# Example 7: Complex key with tuple (ascending age, descending salary)
by_age_asc_salary_desc = sorted(people, key=lambda p: (p.age, -p.salary))
print(by_age_asc_salary_desc)  # [Bob(25), Alice(30), Charlie(30)]
# Alice before Charlie: same age, but 70000 > 60000 (negated gives Alice priority)
 
# Example 8: itemgetter for list-of-lists or list-of-tuples
data = [("apple", 3, 150), ("banana", 1, 100), ("cherry", 2, 200)]
by_second = sorted(data, key=itemgetter(1))
print(by_second)  # [('banana', 1, 100), ('cherry', 2, 200), ('apple', 3, 150)]
 
# Example 9: Converting legacy comparison function
def legacy_compare(a, b):
    """Old-style comparison function"""
    if a.age != b.age:
        return a.age - b.age
    return a.salary - b.salary
 
by_legacy = sorted(people, key=cmp_to_key(legacy_compare))
print(by_legacy)  # Works, but prefer key functions for new code
 
# Example 10: Sorting with None values
items = [3, None, 1, None, 2]
# Put None values at the end
sorted_none_last = sorted(items, key=lambda x: (x is None, x if x is not None else 0))
print(sorted_none_last)  # [1, 2, 3, None, None]

The Tuple Trick for Multi-Criteria Sorting

Python compares tuples lexicographically: first by the first element, then by second if first elements are equal, and so on. This means key=lambda x: (x.age, x.name) sorts by age first, then by name. Use -value within tuples to reverse individual criteria (works for numbers only).

Performance Consideration: Key Caching

Python's sort implementation caches key values, computing each key only once. This means:

# This key function is called O(n) times, not O(n log n) times
sorted(data, key=expensive_computation)

For expensive key computations (database lookups, complex calculations), Python's key-based approach is more efficient than comparison-based approaches in other languages, where the comparison function is called O(n log n) times.

Java's Comparator Interface

Java provides the Comparator<T> interface for custom orderings. Modern Java (8+) offers powerful static factory methods that make comparator creation fluent and readable.

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
import java.util.*;
import java.util.Comparator;
import static java.util.Comparator.*;
 
public class ComparatorExamples {
    public static void main(String[] args) {
        List<Person> people = Arrays.asList(
            new Person("Alice", 30, 70000.0),
            new Person("Bob", 25, 50000.0),
            new Person("Charlie", 30, 60000.0),
            new Person("Diana", 25, 55000.0)
        );
        
        // ===== TRADITIONAL APPROACH (Pre-Java 8) =====
        
        // Anonymous class comparator
        Comparator<Person> byAgeOld = new Comparator<Person>() {
            @Override
            public int compare(Person a, Person b) {
                return Integer.compare(a.getAge(), b.getAge());
            }
        };
        
        // ===== MODERN APPROACH (Java 8+) =====
        
        // Example 1: Lambda expression
        Comparator<Person> byAgeLambda = (a, b) -> Integer.compare(a.getAge(), b.getAge());
        
        // Example 2: Method reference with Comparator.comparing (PREFERRED)
        Comparator<Person> byAge = comparing(Person::getAge);
        
        // Example 3: Chained comparators (multi-field sorting)
        Comparator<Person> byAgeThenSalary = comparing(Person::getAge)
            .thenComparing(Person::getSalary);
        
        // Example 4: Reversed ordering
        Comparator<Person> byAgeDescending = comparing(Person::getAge).reversed();
        
        // Example 5: Mixed ascending/descending
        Comparator<Person> byAgeDescSalaryAsc = comparing(Person::getAge).reversed()
            .thenComparing(Person::getSalary);
        
        // Example 6: Comparing with Comparator for the extracted key
        // Sort by name length, then by name itself
        Comparator<Person> byNameLength = comparing(
            Person::getName, 
            comparingInt(String::length)
        );
        
        // Example 7: Handling nulls
        List<Person> peopleWithNulls = new ArrayList<>(people);
        peopleWithNulls.add(null);  // Add a null person
        
        Comparator<Person> nullsFirst = nullsFirst(comparing(Person::getAge));
        Comparator<Person> nullsLast = nullsLast(comparing(Person::getAge));
        
        // Example 8: Handling null fields
        // If salary could be null
        Comparator<Person> bySalaryNullsFirst = comparing(
            Person::getSalary,
            nullsFirst(naturalOrder())
        );
        
        // Example 9: Using it with sort
        List<Person> sorted = new ArrayList<>(people);
        sorted.sort(comparing(Person::getAge).thenComparing(Person::getName));
        
        // Example 10: Case-insensitive string comparison
        List<String> words = Arrays.asList("Banana", "apple", "Cherry");
        words.sort(String.CASE_INSENSITIVE_ORDER);
        // Result: [apple, Banana, Cherry]
        
        // Example 11: Complex multi-criteria (demonstration)
        // Sort by: in-stock first, then by price ascending, then by name
        Comparator<Product> productSort = comparing(Product::isInStock).reversed()
            .thenComparing(Product::getPrice)
            .thenComparing(Product::getName);
        
        // Example 12: Building comparator conditionally
        boolean sortDescending = true;
        Comparator<Person> dynamicSort = comparing(Person::getAge);
        if (sortDescending) {
            dynamicSort = dynamicSort.reversed();
        }
        
        // Example 13: Using comparingInt/Long/Double for primitives (avoids boxing)
        Comparator<Person> byAgeOptimized = comparingInt(Person::getAge);
        Comparator<Person> bySalaryOptimized = comparingDouble(Person::getSalary);
        
        System.out.println("Original: " + people);
        people.sort(byAgeThenSalary);
        System.out.println("Sorted: " + people);
    }
}
 
class Person {
    private String name;
    private int age;
    private double salary;
    
    Person(String name, int age, double salary) {
        this.name = name;
        this.age = age;
        this.salary = salary;
    }
    
    String getName() { return name; }
    int getAge() { return age; }
    double getSalary() { return salary; }
    
    @Override
    public String toString() {
        return name + "(" + age + ")";
    }
}
 
class Product {
    private String name;
    private double price;
    private boolean inStock;
    
    String getName() { return name; }
    double getPrice() { return price; }
    boolean isInStock() { return inStock; }
}

Prefer comparingInt/Long/Double Over comparing

For primitive fields, use comparingInt(), comparingLong(), or comparingDouble() instead of comparing(). These avoid the overhead of auto-boxing primitives into wrapper objects, which matters for performance-critical sorting of large collections.

The Comparable Interface vs Comparator:

Aspect	Comparable<T>	Comparator<T>
Method	`compareTo(T other)`	`compare(T a, T b)`
Location	Inside the class being compared	External to the class
Use case	Natural ordering	Custom/alternative orderings
Example	`String.compareTo()`	`String.CASE_INSENSITIVE_ORDER`
Flexibility	One ordering per class	Unlimited comparators

Best Practice: Implement Comparable for the natural/default ordering of a class. Create Comparator instances for alternative orderings.

C++'s Boolean Predicates

C++ uses a fundamentally different comparison model: instead of returning -1/0/+1, comparators return a boolean indicating whether the first argument should come before the second.

The Strict Weak Ordering Requirement:

Your predicate must implement strict less-than semantics:

comp(a, a) must return false (irreflexivity)
If comp(a, b) is true, then comp(b, a) must be false (asymmetry)
Transitivity must hold

Critical: Never use <= in a comparison predicate. The standard requires strict inequality (<). Using <= violates irreflexivity since comp(a, a) would return true.

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
#include <algorithm>
#include <vector>
#include <string>
#include <functional>
#include <iostream>
 
struct Person {
    std::string name;
    int age;
    double salary;
};
 
int main() {
    std::vector<Person> people = {
        {"Alice", 30, 70000.0},
        {"Bob", 25, 50000.0},
        {"Charlie", 30, 60000.0},
        {"Diana", 25, 55000.0}
    };
    
    // ===== LAMBDA COMPARATORS =====
    
    // Example 1: Sort by age (ascending)
    std::sort(people.begin(), people.end(), 
        [](const Person& a, const Person& b) {
            return a.age < b.age;  // Note: <, not <=
        });
    
    // Example 2: Sort by age descending
    std::sort(people.begin(), people.end(),
        [](const Person& a, const Person& b) {
            return a.age > b.age;  // Flip the comparison for descending
        });
    
    // Example 3: Multi-field sorting
    std::sort(people.begin(), people.end(),
        [](const Person& a, const Person& b) {
            if (a.age != b.age) return a.age < b.age;
            if (a.salary != b.salary) return a.salary < b.salary;
            return a.name < b.name;
        });
    
    // Example 4: Using std::tie for cleaner multi-field comparison
    std::sort(people.begin(), people.end(),
        [](const Person& a, const Person& b) {
            return std::tie(a.age, a.salary, a.name) 
                 < std::tie(b.age, b.salary, b.name);
        });
    
    // Example 5: Mixed ascending/descending with tie
    // Age ascending, salary descending
    std::sort(people.begin(), people.end(),
        [](const Person& a, const Person& b) {
            if (a.age != b.age) return a.age < b.age;
            return a.salary > b.salary;  // Note: > for descending
        });
    
    // ===== FUNCTOR COMPARATORS =====
    
    // Example 6: Reusable functor class
    struct CompareByAge {
        bool operator()(const Person& a, const Person& b) const {
            return a.age < b.age;
        }
    };
    std::sort(people.begin(), people.end(), CompareByAge{});
    
    // Example 7: Configurable functor
    struct CompareByField {
        enum class Field { AGE, SALARY, NAME };
        Field field;
        bool descending;
        
        CompareByField(Field f, bool desc = false) : field(f), descending(desc) {}
        
        bool operator()(const Person& a, const Person& b) const {
            bool result;
            switch (field) {
                case Field::AGE: result = a.age < b.age; break;
                case Field::SALARY: result = a.salary < b.salary; break;
                case Field::NAME: result = a.name < b.name; break;
            }
            return descending ? !result && !(a.age == b.age) : result;
            // Note: This descending logic is simplified; proper implementation
            // needs more careful handling for equality cases
        }
    };
    
    // ===== STANDARD LIBRARY UTILITIES =====
    
    // Example 8: std::greater for descending order
    std::vector<int> numbers = {3, 1, 4, 1, 5, 9, 2, 6};
    std::sort(numbers.begin(), numbers.end(), std::greater<int>());
    // Result: {9, 6, 5, 4, 3, 2, 1, 1}
    
    // Example 9: Using std::greater<> (transparent comparator, C++14)
    std::sort(numbers.begin(), numbers.end(), std::greater<>());
    
    // Example 10: Stable sort with custom comparator
    std::stable_sort(people.begin(), people.end(),
        [](const Person& a, const Person& b) {
            return a.age < b.age;
        });
    
    // ===== C++20 THREE-WAY COMPARISON =====
    
    // In C++20, the spaceship operator <=> can simplify comparisons
    // Person would define: auto operator<=>(const Person&) const = default;
    
    // Example 11: Partial sort (get k smallest elements sorted)
    std::partial_sort(people.begin(), people.begin() + 2, people.end(),
        [](const Person& a, const Person& b) {
            return a.salary < b.salary;
        });
    // First 2 elements are the lowest-salary people, sorted
    
    // Example 12: nth_element (find median without full sort)
    std::nth_element(people.begin(), people.begin() + people.size()/2, people.end(),
        [](const Person& a, const Person& b) {
            return a.age < b.age;
        });
    // Element at middle position is the median by age
    
    return 0;
}

Critical: Never Use <= in C++ Comparators

Using <= instead of < causes undefined behavior. The sort algorithm may infinite loop, crash, or corrupt memory. This is because comp(a, a) returning true violates the strict weak ordering contract that the algorithm depends on.

C++20 Three-Way Comparison (Spaceship Operator):

C++20 introduced <=> (the "spaceship operator") which returns a comparison category:

auto result = a <=> b;
// result is std::strong_ordering::less, equal, or greater
// or std::weak_ordering, std::partial_ordering

This enables compiler-generated comparison operators:

struct Person {
    std::string name;
    int age;
    
    auto operator<=>(const Person&) const = default;
    // Automatically generates <, <=, >, >=, ==, !=
};

The default comparison compares fields in declaration order (name first, then age).

JavaScript Comparison Patterns

JavaScript's comparison functions return a number indicating the relative ordering. While the specification only requires negative/zero/positive, in practice you'll see patterns that return -1/0/+1 or actual differences.

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
150
151
152
153
154
155
// ===== BASIC PATTERNS =====
 
// Numeric ascending
const ascNum = (a, b) => a - b;
 
// Numeric descending
const descNum = (a, b) => b - a;
 
// String ascending (locale-aware)
const ascStr = (a, b) => a.localeCompare(b);
 
// String descending
const descStr = (a, b) => b.localeCompare(a);
 
// Boolean: true first, then false
const boolTrueFirst = (a, b) => b - a;  // true (1) - false (0) = positive, so false comes "after"
 
// Boolean: false first, then true  
const boolFalseFirst = (a, b) => a - b;
 
 
// ===== OBJECT PROPERTY SORTING =====
 
const products = [
    { name: "Widget", price: 25, inStock: true, rating: 4.5 },
    { name: "Gadget", price: 15, inStock: false, rating: 4.8 },
    { name: "Doohickey", price: 25, inStock: true, rating: 3.9 },
    { name: "Thingamajig", price: 10, inStock: false, rating: 4.5 }
];
 
// Sort by single property
const byPrice = [...products].sort((a, b) => a.price - b.price);
 
// Sort by property descending
const byPriceDesc = [...products].sort((a, b) => b.price - a.price);
 
// Multi-property: price ascending, then rating descending
const byPriceThenRating = [...products].sort((a, b) => {
    if (a.price !== b.price) return a.price - b.price;
    return b.rating - a.rating;  // Descending for rating
});
 
// Multi-property: in-stock first, then price, then name
const byStockPriceName = [...products].sort((a, b) => {
    // in-stock first (true < false in our desired order)
    if (a.inStock !== b.inStock) return a.inStock ? -1 : 1;
    if (a.price !== b.price) return a.price - b.price;
    return a.name.localeCompare(b.name);
});
 
 
// ===== REUSABLE COMPARATOR BUILDERS =====
 
// Factory for property-based comparison
const compareBy = (key, descending = false) => (a, b) => {
    const aVal = typeof key === 'function' ? key(a) : a[key];
    const bVal = typeof key === 'function' ? key(b) : b[key];
    
    let result;
    if (typeof aVal === 'string') {
        result = aVal.localeCompare(bVal);
    } else {
        result = aVal - bVal;
    }
    
    return descending ? -result : result;
};
 
// Usage:
const byRating = [...products].sort(compareBy('rating'));
const byRatingDesc = [...products].sort(compareBy('rating', true));
const byNameLength = [...products].sort(compareBy(p => p.name.length));
 
// Chain multiple comparators
const chainComparators = (...comparators) => (a, b) => {
    for (const compare of comparators) {
        const result = compare(a, b);
        if (result !== 0) return result;
    }
    return 0;
};
 
// Usage:
const complexSort = chainComparators(
    compareBy('price'),
    compareBy('rating', true),
    compareBy('name')
);
const sorted = [...products].sort(complexSort);
 
 
// ===== HANDLING SPECIAL VALUES =====
 
// Handling nulls/undefined (nulls last)
const compareWithNulls = (a, b) => {
    if (a == null && b == null) return 0;
    if (a == null) return 1;  // null goes to end
    if (b == null) return -1;
    return a - b;
};
 
// Handling NaN in numeric comparisons
const compareNumbers = (a, b) => {
    const aIsNaN = Number.isNaN(a);
    const bIsNaN = Number.isNaN(b);
    if (aIsNaN && bIsNaN) return 0;
    if (aIsNaN) return 1;  // NaN goes to end
    if (bIsNaN) return -1;
    return a - b;
};
 
 
// ===== DATE SORTING =====
 
const events = [
    { name: "Conference", date: new Date("2024-06-15") },
    { name: "Meeting", date: new Date("2024-03-01") },
    { name: "Workshop", date: new Date("2024-06-15") },
];
 
// Sort by date (chronological)
const byDate = [...events].sort((a, b) => a.date - b.date);
// Dates can be subtracted to get milliseconds difference
 
// Sort by date, then by name for same dates
const byDateThenName = [...events].sort((a, b) => {
    const dateCompare = a.date - b.date;
    if (dateCompare !== 0) return dateCompare;
    return a.name.localeCompare(b.name);
});
 
 
// ===== COMPLEX SORTING: PRIORITY QUEUE STYLE =====
 
const tasks = [
    { title: "Bug fix", priority: "high", dueDate: new Date("2024-03-15"), completed: false },
    { title: "Feature", priority: "medium", dueDate: new Date("2024-03-01"), completed: false },
    { title: "Docs", priority: "low", dueDate: new Date("2024-03-10"), completed: true },
    { title: "Review", priority: "high", dueDate: new Date("2024-03-05"), completed: false },
];
 
const priorityOrder = { high: 0, medium: 1, low: 2 };
 
// Sort: incomplete first, then by priority, then by due date
const taskSort = [...tasks].sort((a, b) => {
    // Completed tasks go to the end
    if (a.completed !== b.completed) return a.completed ? 1 : -1;
    
    // Among incomplete: sort by priority (high first)
    const priorityDiff = priorityOrder[a.priority] - priorityOrder[b.priority];
    if (priorityDiff !== 0) return priorityDiff;
    
    // Same priority: earlier due date first
    return a.dueDate - b.dueDate;
});

Consistency Is Key

Your comparison function must be consistent: if you compare the same pair of elements multiple times during a single sort, it must always return the same result. Avoid comparisons that depend on external mutable state, random values, or the current time.

Common Comparison Pitfalls and Debugging

Comparison functions are deceptively easy to get wrong. Here are the most common pitfalls and how to avoid them:

The Most Dangerous Comparison Bugs

•Numeric overflow — Using a - b for comparison can overflow for large integers. For example, INT_MIN - 1 wraps around. Use explicit comparisons (a < b ? -1 : a > b ? 1 : 0) for safety.
•Floating-point NaN — NaN compared to anything (including itself) returns false. This breaks transitivity. Handle NaN explicitly or ensure your data doesn't contain NaN.
•Missing return statement — Forgetting to return a value in some branch makes the function return undefined, which may cause inconsistent behavior.
•Inconsistent null/undefined handling — If some objects have missing properties, a.x - b.x might produce NaN. Handle missing values explicitly.
•Case sensitivity surprises — 'Apple' sorts before 'banana' because uppercase letters have lower Unicode values. Use .toLowerCase() or .localeCompare() for expected results.
•Locale-specific ordering — Different locales order characters differently (e.g., 'ä' in German vs Swedish). Use .localeCompare() with explicit locale for consistency.

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
// ❌ BUG: Integer overflow (in languages with fixed-size integers)
const badCompare = (a, b) => a - b;
// In JavaScript: Number.MAX_SAFE_INTEGER - (-Number.MAX_SAFE_INTEGER) = Infinity
// In Java/C++: INT_MAX - INT_MIN = overflow!
 
// ✅ FIX: Use explicit comparisons
const safeCompare = (a, b) => {
    if (a < b) return -1;
    if (a > b) return 1;
    return 0;
};
 
 
// ❌ BUG: NaN breaks transitivity
const data = [3, NaN, 1, NaN, 2];
data.sort((a, b) => a - b);  
// Result is unpredictable because NaN comparisons are always false
 
// ✅ FIX: Handle NaN explicitly
const nanSafeCompare = (a, b) => {
    const aIsNaN = Number.isNaN(a);
    const bIsNaN = Number.isNaN(b);
    if (aIsNaN && bIsNaN) return 0;
    if (aIsNaN) return 1;  // NaN goes to end
    if (bIsNaN) return -1;
    return a - b;
};
 
 
// ❌ BUG: Missing property causes NaN
const items = [
    { name: "A", price: 10 },
    { name: "B" },  // No price!
    { name: "C", price: 5 }
];
items.sort((a, b) => a.price - b.price);
// undefined - 10 = NaN, breaks comparison
 
// ✅ FIX: Handle missing properties
const safePropertyCompare = (a, b) => {
    const aPrice = a.price ?? Infinity;  // Missing = expensive = end
    const bPrice = b.price ?? Infinity;
    return aPrice - bPrice;
};
 
 
// ❌ BUG: Case-sensitivity surprise
const words = ['banana', 'Apple', 'cherry'];
words.sort();  // ['Apple', 'banana', 'cherry']
// 'A' (65) comes before 'b' (98) in ASCII
 
// ✅ FIX: Case-insensitive comparison
words.sort((a, b) => a.toLowerCase().localeCompare(b.toLowerCase()));
// ['Apple', 'banana', 'cherry'] — but respecting original case
 
 
// ❌ BUG: Returning non-consistent values
let counter = 0;
const badCompareStateful = (a, b) => {
    counter++;
    if (counter % 2 === 0) return a - b;
    return b - a;  // Flip every other comparison!
};
 
// ✅ FIX: Always be deterministic
const goodCompare = (a, b) => a - b;  // Same result for same inputs, always
 
 
// ❌ BUG: Forgetting to handle equality in multi-field
const badMulti = (a, b) => {
    if (a.priority < b.priority) return -1;
    if (a.priority > b.priority) return 1;
    // Forgot to compare by next field when priorities are equal!
};
 
// ✅ FIX: Chain all comparison fields
const goodMulti = (a, b) => {
    if (a.priority !== b.priority) return a.priority - b.priority;
    if (a.date !== b.date) return a.date - b.date;
    return a.name.localeCompare(b.name);
};

Debugging Strategy: Add Logging

When debugging comparison issues, temporarily add logging to see what's being compared: console.log(a, b, result). Look for pairs where the result seems wrong, then trace backward to find the logic error. Also verify your function handles self-comparison correctly: compare(x, x) should return 0.

Summary: Mastering Custom Comparisons

Custom comparison functions unlock the full power of library sorting. Let's consolidate the key principles:

Key Takeaways

•Respect the mathematical contract — Comparisons must be irreflexive, asymmetric, and transitive. Violating these properties causes bugs or crashes.
•Know your language's conventions — Python uses key functions, JavaScript returns numbers, C++ uses boolean predicates. Use the right pattern.
•Handle edge cases explicitly — Null values, missing properties, NaN, and empty strings all need deliberate handling.
•Build reusable comparator utilities — Factory functions like compareBy() and chainComparators() make complex sorting maintainable.
•Test with adversarial inputs — Include null, undefined, duplicate values, and extreme values in your test sets.
•Prefer key functions when available — Python's key approach is often cleaner and more efficient than comparison functions.

Quick Reference: Comparison Return Values
Language	a Comes First	Equal	b Comes First
Python (cmp)	-1 (or negative)	0	+1 (or positive)
JavaScript	Negative number	0	Positive number
Java	-1 (or negative)	0	+1 (or positive)
C++	true	false	false
Go	true	false	false
Rust	Ordering::Less	Ordering::Equal	Ordering::Greater

Page Complete

You now understand how to write correct, efficient custom comparison functions across multiple programming languages. In the next page, we'll explore stability guarantees in library implementations—what they mean, when they matter, and how they affect real-world sorting scenarios.

2 / 4

Loading learning content...

Data Structures & AlgorithmsSorting in Practice

Sorting in Practice — Library Functions

LevelIntermediate

Duration60 mins

TopicSorting in Practice

2 / 4

Customizing Comparison Functions

Beyond Default Ordering: The Power of Custom Comparisons

Library sort functions provide sensible defaults—numbers sort numerically, strings sort lexicographically. But real-world applications demand far more sophisticated ordering:

Sort users by activity date descending, then by name ascending
Order products with in-stock items first, then by price
Arrange files with directories before files, then alphabetically
Sort search results by relevance, with sponsored posts first
Order tasks by priority level, then by due date, with overdue items first

What You Will Learn

The Comparison Function Contract

The Three Essential Properties:

A valid comparison function must be a strict weak ordering, which requires three properties:

Mathematical Properties of Valid Comparisons

•Irreflexivity — An element is never "less than" itself: compare(a, a) must indicate equality (return 0, or return false for less-than predicates). No element comes before itself.
•Asymmetry — If a comes before b, then b cannot come before a: if compare(a, b) < 0, then compare(b, a) > 0. Ordering is one-way.
•Transitivity — If a comes before b, and b comes before c, then a must come before c: if compare(a, b) < 0 and compare(b, c) < 0, then compare(a, c) < 0. Ordering chains must be consistent.

A fourth property for equivalence:

Transitivity of Equivalence — If a is equivalent to b, and b is equivalent to c, then a must be equivalent to c. This ensures that "equal" elements form consistent groups.

Why These Rules Matter:

The #1 Comparison Bug

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
// ✅ VALID: Simple numeric comparison
const valid1 = (a, b) => a - b;  // Obeys all three properties
 
// ✅ VALID: String comparison
const valid2 = (a, b) => a.localeCompare(b);  // Built-in is correct
 
// ❌ INVALID: Non-transitive comparison
// This compares by the first digit only
const invalid1 = (a, b) => {
    const firstA = String(a)[0];
    const firstB = String(b)[0];
    return firstA.localeCompare(firstB);
};
// Problem: 19 and 12 are "equal" (both start with 1)
//          12 and 25 are "equal"? No, 1 < 2, so 12 < 25
//          But 19 and 25? 1 < 2, so 19 < 25
// This seems okay... let's try another example:
// 15, 19, 12 — by this logic 15=19=12 (all start with 1)
// But we could end up with [19, 12, 15] or any permutation
// Actually this breaks because it's not a strict ordering at all
 
// ❌ INVALID: Random comparison (non-deterministic)
const invalid2 = (a, b) => Math.random() - 0.5;  // DON'T DO THIS!
// Violates asymmetry: same pair might return different results on each call
 
// ❌ INVALID: Asymmetry violation
const invalid3 = (a, b) => a.priority - b.priority || -1;
// When priorities are equal, always returns -1 (a < b)
// But then compare(b, a) also returns -1 (b < a)!
// Violates asymmetry: both a < b and b < a can't be true
 
// ✅ VALID: Correct multi-field comparison
const valid3 = (a, b) => {
    if (a.priority !== b.priority) {
        return a.priority - b.priority;
    }
    return a.name.localeCompare(b.name);
};

Comparison Function Signatures by Language

Different languages use different conventions for comparison functions. Understanding these conventions is crucial for writing correct comparators.

Comparison Function Conventions Across Languages
Language	Signature	Return Values	Notes
Python	`key=func` or `cmp_to_key`	Key: any comparable value Cmp: -1, 0, +1	Modern Python prefers key functions; cmp_to_key for legacy
JavaScript	`(a, b) => number`	Negative: a first 0: equal Positive: b first	Return actual difference for numbers, not just -1/0/1
Java	`Comparator<T>` interface	-1, 0, +1 (by convention) Any negative/positive works	Use Comparator.comparing() for modern approach
C++	`bool(a, b)` predicate	true: a < b false: a >= b	Strict less-than semantics; NOT a three-way comparison
Go	`func(i, j int) bool`	true: element[i] < element[j] false: otherwise	Operates on indices, not values directly
Rust	`Fn(&T, &T) -> Ordering`	`Less`, `Equal`, `Greater`	Enum provides type safety; can also use key functions

C++'s Boolean Predicate Is Different

Python's Key Functions

Why Key Functions?

Simpler to write — No need to think about -1/0/+1 semantics
Fewer bugs — Key functions can't violate strict weak ordering as easily
More efficient — Key is computed once per element, not once per comparison
Composable — Multiple keys can be combined with tuples

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
from functools import cmp_to_key
from operator import attrgetter, itemgetter
 
# Example 1: Sort strings by length
words = ["apple", "pie", "banana", "strawberry"]
sorted_by_length = sorted(words, key=len)
print(sorted_by_length)  # ['pie', 'apple', 'banana', 'strawberry']
 
# Example 2: Sort case-insensitively
words = ["Banana", "apple", "Cherry"]
sorted_case_insensitive = sorted(words, key=str.lower)
print(sorted_case_insensitive)  # ['apple', 'Banana', 'Cherry']
 
# Example 3: Sort by absolute value
numbers = [-5, 2, -1, 7, -3]
sorted_by_abs = sorted(numbers, key=abs)
print(sorted_by_abs)  # [-1, 2, -3, -5, 7]
 
# Example 4: Sort dictionaries by a specific key
products = [
    {"name": "Widget", "price": 25.99, "stock": 100},
    {"name": "Gadget", "price": 15.99, "stock": 50},
    {"name": "Doohickey", "price": 25.99, "stock": 75},
]
 
# By price
by_price = sorted(products, key=lambda x: x["price"])
print([p["name"] for p in by_price])  # ['Gadget', 'Widget', 'Doohickey']
 
# By price, then by stock (descending) — use tuples!
by_price_then_stock = sorted(products, key=lambda x: (x["price"], -x["stock"]))
print([p["name"] for p in by_price_then_stock])  # ['Gadget', 'Doohickey', 'Widget']
# Doohickey comes before Widget: same price, but 75 > 50 (negated comparison)
 
# Example 5: Sort objects by attribute
class Person:
    def __init__(self, name, age, salary):
        self.name = name
        self.age = age
        self.salary = salary
    def __repr__(self):
        return f"{self.name}({self.age})"
 
people = [
    Person("Alice", 30, 70000),
    Person("Bob", 25, 50000),
    Person("Charlie", 30, 60000),
]
 
# Using lambda
by_age = sorted(people, key=lambda p: p.age)
print(by_age)  # [Bob(25), Alice(30), Charlie(30)]
 
# Using attrgetter (faster for frequently-used sorts)
by_age_v2 = sorted(people, key=attrgetter("age"))
print(by_age_v2)  # [Bob(25), Alice(30), Charlie(30)]
 
# Multiple attributes
by_age_then_salary = sorted(people, key=attrgetter("age", "salary"))
print(by_age_then_salary)  # [Bob(25), Charlie(30), Alice(30)]
# Charlie before Alice: same age, but 60000 < 70000
 
# Example 6: Descending order
by_age_desc = sorted(people, key=lambda p: p.age, reverse=True)
print(by_age_desc)  # [Alice(30), Charlie(30), Bob(25)]
 
# Example 7: Complex key with tuple (ascending age, descending salary)
by_age_asc_salary_desc = sorted(people, key=lambda p: (p.age, -p.salary))
print(by_age_asc_salary_desc)  # [Bob(25), Alice(30), Charlie(30)]
# Alice before Charlie: same age, but 70000 > 60000 (negated gives Alice priority)
 
# Example 8: itemgetter for list-of-lists or list-of-tuples
data = [("apple", 3, 150), ("banana", 1, 100), ("cherry", 2, 200)]
by_second = sorted(data, key=itemgetter(1))
print(by_second)  # [('banana', 1, 100), ('cherry', 2, 200), ('apple', 3, 150)]
 
# Example 9: Converting legacy comparison function
def legacy_compare(a, b):
    """Old-style comparison function"""
    if a.age != b.age:
        return a.age - b.age
    return a.salary - b.salary
 
by_legacy = sorted(people, key=cmp_to_key(legacy_compare))
print(by_legacy)  # Works, but prefer key functions for new code
 
# Example 10: Sorting with None values
items = [3, None, 1, None, 2]
# Put None values at the end
sorted_none_last = sorted(items, key=lambda x: (x is None, x if x is not None else 0))
print(sorted_none_last)  # [1, 2, 3, None, None]

The Tuple Trick for Multi-Criteria Sorting

Performance Consideration: Key Caching

Python's sort implementation caches key values, computing each key only once. This means:

# This key function is called O(n) times, not O(n log n) times
sorted(data, key=expensive_computation)

Java's Comparator Interface

Java provides the Comparator<T> interface for custom orderings. Modern Java (8+) offers powerful static factory methods that make comparator creation fluent and readable.

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
import java.util.*;
import java.util.Comparator;
import static java.util.Comparator.*;
 
public class ComparatorExamples {
    public static void main(String[] args) {
        List<Person> people = Arrays.asList(
            new Person("Alice", 30, 70000.0),
            new Person("Bob", 25, 50000.0),
            new Person("Charlie", 30, 60000.0),
            new Person("Diana", 25, 55000.0)
        );
        
        // ===== TRADITIONAL APPROACH (Pre-Java 8) =====
        
        // Anonymous class comparator
        Comparator<Person> byAgeOld = new Comparator<Person>() {
            @Override
            public int compare(Person a, Person b) {
                return Integer.compare(a.getAge(), b.getAge());
            }
        };
        
        // ===== MODERN APPROACH (Java 8+) =====
        
        // Example 1: Lambda expression
        Comparator<Person> byAgeLambda = (a, b) -> Integer.compare(a.getAge(), b.getAge());
        
        // Example 2: Method reference with Comparator.comparing (PREFERRED)
        Comparator<Person> byAge = comparing(Person::getAge);
        
        // Example 3: Chained comparators (multi-field sorting)
        Comparator<Person> byAgeThenSalary = comparing(Person::getAge)
            .thenComparing(Person::getSalary);
        
        // Example 4: Reversed ordering
        Comparator<Person> byAgeDescending = comparing(Person::getAge).reversed();
        
        // Example 5: Mixed ascending/descending
        Comparator<Person> byAgeDescSalaryAsc = comparing(Person::getAge).reversed()
            .thenComparing(Person::getSalary);
        
        // Example 6: Comparing with Comparator for the extracted key
        // Sort by name length, then by name itself
        Comparator<Person> byNameLength = comparing(
            Person::getName, 
            comparingInt(String::length)
        );
        
        // Example 7: Handling nulls
        List<Person> peopleWithNulls = new ArrayList<>(people);
        peopleWithNulls.add(null);  // Add a null person
        
        Comparator<Person> nullsFirst = nullsFirst(comparing(Person::getAge));
        Comparator<Person> nullsLast = nullsLast(comparing(Person::getAge));
        
        // Example 8: Handling null fields
        // If salary could be null
        Comparator<Person> bySalaryNullsFirst = comparing(
            Person::getSalary,
            nullsFirst(naturalOrder())
        );
        
        // Example 9: Using it with sort
        List<Person> sorted = new ArrayList<>(people);
        sorted.sort(comparing(Person::getAge).thenComparing(Person::getName));
        
        // Example 10: Case-insensitive string comparison
        List<String> words = Arrays.asList("Banana", "apple", "Cherry");
        words.sort(String.CASE_INSENSITIVE_ORDER);
        // Result: [apple, Banana, Cherry]
        
        // Example 11: Complex multi-criteria (demonstration)
        // Sort by: in-stock first, then by price ascending, then by name
        Comparator<Product> productSort = comparing(Product::isInStock).reversed()
            .thenComparing(Product::getPrice)
            .thenComparing(Product::getName);
        
        // Example 12: Building comparator conditionally
        boolean sortDescending = true;
        Comparator<Person> dynamicSort = comparing(Person::getAge);
        if (sortDescending) {
            dynamicSort = dynamicSort.reversed();
        }
        
        // Example 13: Using comparingInt/Long/Double for primitives (avoids boxing)
        Comparator<Person> byAgeOptimized = comparingInt(Person::getAge);
        Comparator<Person> bySalaryOptimized = comparingDouble(Person::getSalary);
        
        System.out.println("Original: " + people);
        people.sort(byAgeThenSalary);
        System.out.println("Sorted: " + people);
    }
}
 
class Person {
    private String name;
    private int age;
    private double salary;
    
    Person(String name, int age, double salary) {
        this.name = name;
        this.age = age;
        this.salary = salary;
    }
    
    String getName() { return name; }
    int getAge() { return age; }
    double getSalary() { return salary; }
    
    @Override
    public String toString() {
        return name + "(" + age + ")";
    }
}
 
class Product {
    private String name;
    private double price;
    private boolean inStock;
    
    String getName() { return name; }
    double getPrice() { return price; }
    boolean isInStock() { return inStock; }
}

Prefer comparingInt/Long/Double Over comparing

The Comparable Interface vs Comparator:

Aspect	Comparable<T>	Comparator<T>
Method	`compareTo(T other)`	`compare(T a, T b)`
Location	Inside the class being compared	External to the class
Use case	Natural ordering	Custom/alternative orderings
Example	`String.compareTo()`	`String.CASE_INSENSITIVE_ORDER`
Flexibility	One ordering per class	Unlimited comparators

Best Practice: Implement Comparable for the natural/default ordering of a class. Create Comparator instances for alternative orderings.

C++'s Boolean Predicates

C++ uses a fundamentally different comparison model: instead of returning -1/0/+1, comparators return a boolean indicating whether the first argument should come before the second.

The Strict Weak Ordering Requirement:

Your predicate must implement strict less-than semantics:

comp(a, a) must return false (irreflexivity)
If comp(a, b) is true, then comp(b, a) must be false (asymmetry)
Transitivity must hold

Critical: Never use <= in a comparison predicate. The standard requires strict inequality (<). Using <= violates irreflexivity since comp(a, a) would return true.

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
#include <algorithm>
#include <vector>
#include <string>
#include <functional>
#include <iostream>
 
struct Person {
    std::string name;
    int age;
    double salary;
};
 
int main() {
    std::vector<Person> people = {
        {"Alice", 30, 70000.0},
        {"Bob", 25, 50000.0},
        {"Charlie", 30, 60000.0},
        {"Diana", 25, 55000.0}
    };
    
    // ===== LAMBDA COMPARATORS =====
    
    // Example 1: Sort by age (ascending)
    std::sort(people.begin(), people.end(), 
        [](const Person& a, const Person& b) {
            return a.age < b.age;  // Note: <, not <=
        });
    
    // Example 2: Sort by age descending
    std::sort(people.begin(), people.end(),
        [](const Person& a, const Person& b) {
            return a.age > b.age;  // Flip the comparison for descending
        });
    
    // Example 3: Multi-field sorting
    std::sort(people.begin(), people.end(),
        [](const Person& a, const Person& b) {
            if (a.age != b.age) return a.age < b.age;
            if (a.salary != b.salary) return a.salary < b.salary;
            return a.name < b.name;
        });
    
    // Example 4: Using std::tie for cleaner multi-field comparison
    std::sort(people.begin(), people.end(),
        [](const Person& a, const Person& b) {
            return std::tie(a.age, a.salary, a.name) 
                 < std::tie(b.age, b.salary, b.name);
        });
    
    // Example 5: Mixed ascending/descending with tie
    // Age ascending, salary descending
    std::sort(people.begin(), people.end(),
        [](const Person& a, const Person& b) {
            if (a.age != b.age) return a.age < b.age;
            return a.salary > b.salary;  // Note: > for descending
        });
    
    // ===== FUNCTOR COMPARATORS =====
    
    // Example 6: Reusable functor class
    struct CompareByAge {
        bool operator()(const Person& a, const Person& b) const {
            return a.age < b.age;
        }
    };
    std::sort(people.begin(), people.end(), CompareByAge{});
    
    // Example 7: Configurable functor
    struct CompareByField {
        enum class Field { AGE, SALARY, NAME };
        Field field;
        bool descending;
        
        CompareByField(Field f, bool desc = false) : field(f), descending(desc) {}
        
        bool operator()(const Person& a, const Person& b) const {
            bool result;
            switch (field) {
                case Field::AGE: result = a.age < b.age; break;
                case Field::SALARY: result = a.salary < b.salary; break;
                case Field::NAME: result = a.name < b.name; break;
            }
            return descending ? !result && !(a.age == b.age) : result;
            // Note: This descending logic is simplified; proper implementation
            // needs more careful handling for equality cases
        }
    };
    
    // ===== STANDARD LIBRARY UTILITIES =====
    
    // Example 8: std::greater for descending order
    std::vector<int> numbers = {3, 1, 4, 1, 5, 9, 2, 6};
    std::sort(numbers.begin(), numbers.end(), std::greater<int>());
    // Result: {9, 6, 5, 4, 3, 2, 1, 1}
    
    // Example 9: Using std::greater<> (transparent comparator, C++14)
    std::sort(numbers.begin(), numbers.end(), std::greater<>());
    
    // Example 10: Stable sort with custom comparator
    std::stable_sort(people.begin(), people.end(),
        [](const Person& a, const Person& b) {
            return a.age < b.age;
        });
    
    // ===== C++20 THREE-WAY COMPARISON =====
    
    // In C++20, the spaceship operator <=> can simplify comparisons
    // Person would define: auto operator<=>(const Person&) const = default;
    
    // Example 11: Partial sort (get k smallest elements sorted)
    std::partial_sort(people.begin(), people.begin() + 2, people.end(),
        [](const Person& a, const Person& b) {
            return a.salary < b.salary;
        });
    // First 2 elements are the lowest-salary people, sorted
    
    // Example 12: nth_element (find median without full sort)
    std::nth_element(people.begin(), people.begin() + people.size()/2, people.end(),
        [](const Person& a, const Person& b) {
            return a.age < b.age;
        });
    // Element at middle position is the median by age
    
    return 0;
}

Critical: Never Use <= in C++ Comparators

C++20 Three-Way Comparison (Spaceship Operator):

C++20 introduced <=> (the "spaceship operator") which returns a comparison category:

auto result = a <=> b;
// result is std::strong_ordering::less, equal, or greater
// or std::weak_ordering, std::partial_ordering

This enables compiler-generated comparison operators:

struct Person {
    std::string name;
    int age;
    
    auto operator<=>(const Person&) const = default;
    // Automatically generates <, <=, >, >=, ==, !=
};

The default comparison compares fields in declaration order (name first, then age).

JavaScript Comparison Patterns

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
150
151
152
153
154
155
// ===== BASIC PATTERNS =====
 
// Numeric ascending
const ascNum = (a, b) => a - b;
 
// Numeric descending
const descNum = (a, b) => b - a;
 
// String ascending (locale-aware)
const ascStr = (a, b) => a.localeCompare(b);
 
// String descending
const descStr = (a, b) => b.localeCompare(a);
 
// Boolean: true first, then false
const boolTrueFirst = (a, b) => b - a;  // true (1) - false (0) = positive, so false comes "after"
 
// Boolean: false first, then true  
const boolFalseFirst = (a, b) => a - b;
 
 
// ===== OBJECT PROPERTY SORTING =====
 
const products = [
    { name: "Widget", price: 25, inStock: true, rating: 4.5 },
    { name: "Gadget", price: 15, inStock: false, rating: 4.8 },
    { name: "Doohickey", price: 25, inStock: true, rating: 3.9 },
    { name: "Thingamajig", price: 10, inStock: false, rating: 4.5 }
];
 
// Sort by single property
const byPrice = [...products].sort((a, b) => a.price - b.price);
 
// Sort by property descending
const byPriceDesc = [...products].sort((a, b) => b.price - a.price);
 
// Multi-property: price ascending, then rating descending
const byPriceThenRating = [...products].sort((a, b) => {
    if (a.price !== b.price) return a.price - b.price;
    return b.rating - a.rating;  // Descending for rating
});
 
// Multi-property: in-stock first, then price, then name
const byStockPriceName = [...products].sort((a, b) => {
    // in-stock first (true < false in our desired order)
    if (a.inStock !== b.inStock) return a.inStock ? -1 : 1;
    if (a.price !== b.price) return a.price - b.price;
    return a.name.localeCompare(b.name);
});
 
 
// ===== REUSABLE COMPARATOR BUILDERS =====
 
// Factory for property-based comparison
const compareBy = (key, descending = false) => (a, b) => {
    const aVal = typeof key === 'function' ? key(a) : a[key];
    const bVal = typeof key === 'function' ? key(b) : b[key];
    
    let result;
    if (typeof aVal === 'string') {
        result = aVal.localeCompare(bVal);
    } else {
        result = aVal - bVal;
    }
    
    return descending ? -result : result;
};
 
// Usage:
const byRating = [...products].sort(compareBy('rating'));
const byRatingDesc = [...products].sort(compareBy('rating', true));
const byNameLength = [...products].sort(compareBy(p => p.name.length));
 
// Chain multiple comparators
const chainComparators = (...comparators) => (a, b) => {
    for (const compare of comparators) {
        const result = compare(a, b);
        if (result !== 0) return result;
    }
    return 0;
};
 
// Usage:
const complexSort = chainComparators(
    compareBy('price'),
    compareBy('rating', true),
    compareBy('name')
);
const sorted = [...products].sort(complexSort);
 
 
// ===== HANDLING SPECIAL VALUES =====
 
// Handling nulls/undefined (nulls last)
const compareWithNulls = (a, b) => {
    if (a == null && b == null) return 0;
    if (a == null) return 1;  // null goes to end
    if (b == null) return -1;
    return a - b;
};
 
// Handling NaN in numeric comparisons
const compareNumbers = (a, b) => {
    const aIsNaN = Number.isNaN(a);
    const bIsNaN = Number.isNaN(b);
    if (aIsNaN && bIsNaN) return 0;
    if (aIsNaN) return 1;  // NaN goes to end
    if (bIsNaN) return -1;
    return a - b;
};
 
 
// ===== DATE SORTING =====
 
const events = [
    { name: "Conference", date: new Date("2024-06-15") },
    { name: "Meeting", date: new Date("2024-03-01") },
    { name: "Workshop", date: new Date("2024-06-15") },
];
 
// Sort by date (chronological)
const byDate = [...events].sort((a, b) => a.date - b.date);
// Dates can be subtracted to get milliseconds difference
 
// Sort by date, then by name for same dates
const byDateThenName = [...events].sort((a, b) => {
    const dateCompare = a.date - b.date;
    if (dateCompare !== 0) return dateCompare;
    return a.name.localeCompare(b.name);
});
 
 
// ===== COMPLEX SORTING: PRIORITY QUEUE STYLE =====
 
const tasks = [
    { title: "Bug fix", priority: "high", dueDate: new Date("2024-03-15"), completed: false },
    { title: "Feature", priority: "medium", dueDate: new Date("2024-03-01"), completed: false },
    { title: "Docs", priority: "low", dueDate: new Date("2024-03-10"), completed: true },
    { title: "Review", priority: "high", dueDate: new Date("2024-03-05"), completed: false },
];
 
const priorityOrder = { high: 0, medium: 1, low: 2 };
 
// Sort: incomplete first, then by priority, then by due date
const taskSort = [...tasks].sort((a, b) => {
    // Completed tasks go to the end
    if (a.completed !== b.completed) return a.completed ? 1 : -1;
    
    // Among incomplete: sort by priority (high first)
    const priorityDiff = priorityOrder[a.priority] - priorityOrder[b.priority];
    if (priorityDiff !== 0) return priorityDiff;
    
    // Same priority: earlier due date first
    return a.dueDate - b.dueDate;
});

Consistency Is Key

Common Comparison Pitfalls and Debugging

Comparison functions are deceptively easy to get wrong. Here are the most common pitfalls and how to avoid them:

The Most Dangerous Comparison Bugs

•Numeric overflow — Using a - b for comparison can overflow for large integers. For example, INT_MIN - 1 wraps around. Use explicit comparisons (a < b ? -1 : a > b ? 1 : 0) for safety.
•Floating-point NaN — NaN compared to anything (including itself) returns false. This breaks transitivity. Handle NaN explicitly or ensure your data doesn't contain NaN.
•Missing return statement — Forgetting to return a value in some branch makes the function return undefined, which may cause inconsistent behavior.
•Inconsistent null/undefined handling — If some objects have missing properties, a.x - b.x might produce NaN. Handle missing values explicitly.
•Case sensitivity surprises — 'Apple' sorts before 'banana' because uppercase letters have lower Unicode values. Use .toLowerCase() or .localeCompare() for expected results.
•Locale-specific ordering — Different locales order characters differently (e.g., 'ä' in German vs Swedish). Use .localeCompare() with explicit locale for consistency.

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
// ❌ BUG: Integer overflow (in languages with fixed-size integers)
const badCompare = (a, b) => a - b;
// In JavaScript: Number.MAX_SAFE_INTEGER - (-Number.MAX_SAFE_INTEGER) = Infinity
// In Java/C++: INT_MAX - INT_MIN = overflow!
 
// ✅ FIX: Use explicit comparisons
const safeCompare = (a, b) => {
    if (a < b) return -1;
    if (a > b) return 1;
    return 0;
};
 
 
// ❌ BUG: NaN breaks transitivity
const data = [3, NaN, 1, NaN, 2];
data.sort((a, b) => a - b);  
// Result is unpredictable because NaN comparisons are always false
 
// ✅ FIX: Handle NaN explicitly
const nanSafeCompare = (a, b) => {
    const aIsNaN = Number.isNaN(a);
    const bIsNaN = Number.isNaN(b);
    if (aIsNaN && bIsNaN) return 0;
    if (aIsNaN) return 1;  // NaN goes to end
    if (bIsNaN) return -1;
    return a - b;
};
 
 
// ❌ BUG: Missing property causes NaN
const items = [
    { name: "A", price: 10 },
    { name: "B" },  // No price!
    { name: "C", price: 5 }
];
items.sort((a, b) => a.price - b.price);
// undefined - 10 = NaN, breaks comparison
 
// ✅ FIX: Handle missing properties
const safePropertyCompare = (a, b) => {
    const aPrice = a.price ?? Infinity;  // Missing = expensive = end
    const bPrice = b.price ?? Infinity;
    return aPrice - bPrice;
};
 
 
// ❌ BUG: Case-sensitivity surprise
const words = ['banana', 'Apple', 'cherry'];
words.sort();  // ['Apple', 'banana', 'cherry']
// 'A' (65) comes before 'b' (98) in ASCII
 
// ✅ FIX: Case-insensitive comparison
words.sort((a, b) => a.toLowerCase().localeCompare(b.toLowerCase()));
// ['Apple', 'banana', 'cherry'] — but respecting original case
 
 
// ❌ BUG: Returning non-consistent values
let counter = 0;
const badCompareStateful = (a, b) => {
    counter++;
    if (counter % 2 === 0) return a - b;
    return b - a;  // Flip every other comparison!
};
 
// ✅ FIX: Always be deterministic
const goodCompare = (a, b) => a - b;  // Same result for same inputs, always
 
 
// ❌ BUG: Forgetting to handle equality in multi-field
const badMulti = (a, b) => {
    if (a.priority < b.priority) return -1;
    if (a.priority > b.priority) return 1;
    // Forgot to compare by next field when priorities are equal!
};
 
// ✅ FIX: Chain all comparison fields
const goodMulti = (a, b) => {
    if (a.priority !== b.priority) return a.priority - b.priority;
    if (a.date !== b.date) return a.date - b.date;
    return a.name.localeCompare(b.name);
};

Debugging Strategy: Add Logging

Summary: Mastering Custom Comparisons

Custom comparison functions unlock the full power of library sorting. Let's consolidate the key principles:

Key Takeaways

•Respect the mathematical contract — Comparisons must be irreflexive, asymmetric, and transitive. Violating these properties causes bugs or crashes.
•Know your language's conventions — Python uses key functions, JavaScript returns numbers, C++ uses boolean predicates. Use the right pattern.
•Handle edge cases explicitly — Null values, missing properties, NaN, and empty strings all need deliberate handling.
•Build reusable comparator utilities — Factory functions like compareBy() and chainComparators() make complex sorting maintainable.
•Test with adversarial inputs — Include null, undefined, duplicate values, and extreme values in your test sets.
•Prefer key functions when available — Python's key approach is often cleaner and more efficient than comparison functions.

Quick Reference: Comparison Return Values
Language	a Comes First	Equal	b Comes First
Python (cmp)	-1 (or negative)	0	+1 (or positive)
JavaScript	Negative number	0	Positive number
Java	-1 (or negative)	0	+1 (or positive)
C++	true	false	false
Go	true	false	false
Rust	Ordering::Less	Ordering::Equal	Ordering::Greater

Page Complete

2 / 4