Stable sorting and the built-in sort

Code in:JavaC#PythonJavaScript

In short: A stable sort keeps elements with equal keys in their original order; in Java List.sort is stable, so sorting by several keys works with several sorts or one Comparator.

Problem

The dates that get scrambled

In the shop's admin panel the orders are by date: the oldest at the top. A member of staff clicks the "Customer" heading to see each customer's orders together. They expect Ivan's orders to be one below the other, and still by date.

Here is what a sort by customer with selection sort gives:

record Order(String date, String customer, double amount) {}

static boolean before(Order x, Order y) {
    return x.customer().compareTo(y.customer()) < 0;
}

static void selectionSort(Order[] orders) {
    for (int i = 0; i < orders.length - 1; i++) {
        int smallest = i;
        for (int j = i + 1; j < orders.length; j++) {
            if (before(orders[j], orders[smallest])) {
                smallest = j;
            }
        }
        Order tmp = orders[i];
        orders[i] = orders[smallest];
        orders[smallest] = tmp;
    }
}

Order[] orders = {
    new Order("2026-10-03", "Ivan", 42.50),
    new Order("2026-10-05", "Maria", 18.00),
    new Order("2026-10-07", "Ivan", 120.00),
    new Order("2026-10-09", "Peter", 64.90),
    new Order("2026-10-12", "Maria", 35.20),
    new Order("2026-10-15", "Ivan", 9.99)
};
selectionSort(orders);
for (Order o : orders) {
    System.out.println(o.customer() + " " + o.date());
}

Output

Ivan 2026-10-03
Ivan 2026-10-07
Ivan 2026-10-15
Maria 2026-10-12
Maria 2026-10-05
Peter 2026-10-09

The customers are sorted. But for Maria the order from October 12 comes before the one from October 5. The member of staff sees Maria's last order as the first one and calls her about the wrong one.

The idea

Stability: equal keys keep their order

A sort is stable if elements with an equal key stay in the order they were in. Maria's two orders have an equal key (the customer). A stable sort leaves them as they came: first October 5, then the 12th.

Which algorithms are stable:

• insertion sort: it moves an element only past strictly bigger ones, so it never jumps over an equal one;
• merge sort: on a tie it takes from the left half (merge sort);
• counting sort: it places left to right (counting sort).

Which are not:

• selection sort, quick sort and heap sort. All three swap elements at a distance. The swap carries an element over everything between the two places, and the equal ones in between are left behind it.

Stability matters only when the element carries more than the key. Two equal numbers 5 cannot be told apart. Two orders of Maria can.

See it

Selection sort against insertion sort

The same list with insertion sort:

static void insertionSort(Order[] orders) {
    for (int i = 1; i < orders.length; i++) {
        Order current = orders[i];
        int j = i - 1;
        while (j >= 0 && before(current, orders[j])) {
            orders[j + 1] = orders[j];
            j--;
        }
        orders[j + 1] = current;
    }
}

Order[] orders = {
    new Order("2026-10-03", "Ivan", 42.50),
    new Order("2026-10-05", "Maria", 18.00),
    new Order("2026-10-07", "Ivan", 120.00),
    new Order("2026-10-09", "Peter", 64.90),
    new Order("2026-10-12", "Maria", 35.20),
    new Order("2026-10-15", "Ivan", 9.99)
};
insertionSort(orders);
for (Order o : orders) {
    System.out.println(o.customer() + " " + o.date());
}

Output

Ivan 2026-10-03
Ivan 2026-10-07
Ivan 2026-10-15
Maria 2026-10-05
Maria 2026-10-12
Peter 2026-10-09

static void selectionSort(Order[] orders) {
    for (int i = 0; i < orders.length - 1; i++) {
        int smallest = i;
        for (int j = i + 1; j < orders.length; j++) {
            if (before(orders[j], orders[smallest])) {
                smallest = j;
            }
        }
        Order tmp = orders[i];
        orders[i] = orders[smallest];
        orders[smallest] = tmp;
    }
}

Step by step, in words

1. Six orders, sorted by date. Now by customer, with selection sort.
2. Place 0: the smallest customer from here on is Ivan 10-03, already in place.
3. Place 1: Ivan 10-07 swaps with Maria 10-05.
4. Place 2: Ivan 10-15 swaps with Maria 10-05. The long swap throws Maria 10-05 to the end, over Maria 10-12.
5. Two more swaps: Maria comes before Peter.
6. Sorted by customer, but Maria 10-12 is before Maria 10-05. Selection sort is not stable: equal keys can lose their order.
7. The same list with insertion sort. An order moves only past strictly bigger ones, so Maria 10-05 stays before Maria 10-12. Stable.

The order insertion sort moves to the left stops in front of the first one that is not bigger. An equal order is not jumped over, and Maria's dates stay 05, then 12.

Try it

Find the bug

Someone changed one comparison in insertion sort. The sort is still by customer, but the dates inside each customer come out reversed:

static void insertionSort(Order[] orders) {
    for (int i = 1; i < orders.length; i++) {
        Order current = orders[i];
        int j = i - 1;
        while (j >= 0 && !before(orders[j], current)) {
            orders[j + 1] = orders[j];
            j--;
        }
        orders[j + 1] = current;
    }
}

Order[] orders = {
    new Order("2026-10-03", "Ivan", 42.50),
    new Order("2026-10-05", "Maria", 18.00),
    new Order("2026-10-07", "Ivan", 120.00),
    new Order("2026-10-09", "Peter", 64.90),
    new Order("2026-10-12", "Maria", 35.20),
    new Order("2026-10-15", "Ivan", 9.99)
};
insertionSort(orders);
for (Order o : orders) {
    System.out.println(o.customer() + " " + o.date());
}

Output

Ivan 2026-10-15
Ivan 2026-10-07
Ivan 2026-10-03
Maria 2026-10-12
Maria 2026-10-05
Peter 2026-10-09

Which line is the bug on?

Pick the line with the bug.

1static void insertionSort(Order[] orders) {2 for (int i = 1; i < orders.length; i++) {3 Order current = orders[i];4 int j = i - 1;5 while (j >= 0 && !before(orders[j], current)) {6 orders[j + 1] = orders[j];7 j--;8 }9 orders[j + 1] = current;10 }11}

Check

See it

The built-in sort

In practice you do not write your own sort, you use the built-in one. Twenty orders, by date, sorted by customer. The dates of each customer are printed:

In Java List.sort (and Collections.sort, and Arrays.sort for an array of objects) is stable. The documentation promises it explicitly.

orders.sort(Comparator.comparing(Order::customer));
show(orders);

Output

Ivan: 01 04 06 09 12 15 18
Maria: 02 05 08 11 13 16 19
Peter: 03 07 10 14 17 20

The dates of each customer are in order: 01, 04, 06…

The idea

What the built-in sort of each language uses

• Java. Arrays.sort for an array of primitives (int[], double[]) is dual-pivot quick sort: not stable, but with numbers that does not matter. For objects (Arrays.sort(Object[]), List.sort, Collections.sort) it is TimSort: stable.
• C#. Array.Sort and List<T>.Sort are introsort: quick sort that switches to heap sort when the partitioning gets too deep and to insertion sort for small parts. Not stable. LINQ OrderBy and ThenBy are stable.
• Python. list.sort and sorted are TimSort: stable.
• JavaScript. Array.prototype.sort has to be stable since ES2019. V8 (Chrome, Node.js) uses TimSort from version 7.0.

TimSort is a merge sort that looks for already sorted pieces in the input and merges them. Real data is often almost sorted, and then it is close to O(n).

More precisely, if you are curious

• Python: from version 3.11 the rule by which TimSort chooses which pieces to merge is powersort (by Munro and Wild). The sort is still stable, the merges are better ordered.
• Java: stability really does not matter for primitives, because two equal ints cannot be told apart. That is why the faster quick sort was chosen there.
• C#: introsort keeps O(n log n) in the worst case thanks to heap sort (heap sort). The price is stability.
• JavaScript: before ES2019 V8 used quick sort for long arrays and the sort was not stable. Code written back then sometimes has "fixes" for it that are not needed today.
• In all four: the comparison has to be consistent. If it says that A is before B and B is before A, the result is unpredictable, and in Java List.sort can throw IllegalArgumentException: Comparison method violates its general contract!.

See it

Sorting by several keys

Often the key is more than one field: by customer, and inside each customer the biggest amount first.

Comparator.comparing makes a comparison by one field, thenComparing adds the next one for when the first is equal, and Comparator.reverseOrder() reverses it.

orders.sort(Comparator.comparing(Order::customer)
        .thenComparing(Order::amount, Comparator.reverseOrder()));

Output

Ivan 2026-10-07 €120.00
Ivan 2026-10-03 €42.50
Ivan 2026-10-15 €9.99
Maria 2026-10-12 €35.20
Maria 2026-10-05 €18.00
Peter 2026-10-09 €64.90

There is a second way, which only works with a stable sort: sort first by the second key, then by the first one. The second sort keeps the order of equal keys, and that order is already by the second key. The last sort is the main one.

More precisely, if you are curious

When the second way is useful: when the keys do not fit in one comparison. For example in Python -o.amount does not work for text: for "by customer, and inside each by product name in reverse order" you sort twice, first key=lambda o: o.product, reverse=True, then key=lambda o: o.customer.

Try it

Predict the output

Two stable sorts one after the other: first by amount, the biggest first, then by customer. What does the program print?

List<Order> orders = new ArrayList<>(List.of(
    new Order("2026-10-05", "Maria", 35.20),
    new Order("2026-10-06", "Ivan", 9.99),
    new Order("2026-10-07", "Maria", 18.00),
    new Order("2026-10-08", "Ivan", 42.50)
));
orders.sort(Comparator.comparing(Order::amount).reversed());
orders.sort(Comparator.comparing(Order::customer));
for (Order o : orders) {
    System.out.println(o.customer() + " " + o.amount());
}

Answer

Ivan 42.5 / Ivan 9.99 / Maria 35.2 / Maria 18.0

Ivan 9.99 / Ivan 42.5 / Maria 18.0 / Maria 35.2

Ivan 42.5 / Maria 35.2 / Maria 18.0 / Ivan 9.99

Check

Exercise

Deliveries by city

Solve the task in your editor.

By city, then by amount. Six deliveries have a city and an amount. Sort them by city, and within one city the biggest amount first, with the built-in sort of your language.

Output

Plovdiv €24.00
Plovdiv €15.30
Sofia €80.00
Sofia €12.50
Varna €40.00
Varna €9.90

More tasks

• Twice. Do the same with two stable sorts, without putting two keys into one comparison. Which sort comes first?
• Unstable by hand. Sort the deliveries by city with heap sort from the lesson on heaps. Do the amounts in one city stay in the order they were in?
• A stable selection sort. Can selection sort become stable if, instead of swapping, it moves the smallest one to its place and pushes the rest to the right? What does that cost?

Test

Check yourself

1. What does it mean that a sort is stable?

It is always O(n log n)It needs no extra memoryElements with an equal key stay in the order they were in before

2. Which of these are stable, as they are usually written?

Selection sort and heap sortQuick sort and selection sortInsertion sort and merge sort

3. The list is sorted by date. You want it by customer, and inside each customer by date. What is enough?

One stable sort by customerOne sort by customer with any algorithmNothing is enough, you need a sort by two keys

4. In C# you need a stable sort of orders by customer. What do you use?

OrderBy from LINQArray.Sort with a ComparisonList.Sort

Check

Start the lesson over

Related lessons

• Builds on: Merge sort and "divide and conquer" · Quick sort and the bad pivot · Heap and heap sort · Counting sort and radix sort
• Continues in: Priority queue · Trie · Minimum spanning tree · How to recognise a DP task
• Tasks on this topic: Sorting