Sorting — Stability, Hybrids and Choosing the Best Algorithm

Start here Speed is not the only thing that matters when sorting. Sometimes we need the sort to be stable (not disturb an earlier order), sometimes we want to move data as little as possible, and sometimes the data is too big to fit in memory. This page wraps up sorting: which algorithm to use, when, and why real libraries mix two algorithms together.

Stable sorting #

Real data is often a list of records (tuples), like rows of a table:

This list is already sorted by roll number. Now we sort it by name.

There are two Ashas (101 and 103) and two Ravis (102 and 105). After sorting by name, will each pair still be in roll-number order?

A sort is stable if items with equal keys stay in the same order as before.

Why it matters: sorting on column B should not disturb an earlier sort on column A. For example, in a spreadsheet you sort by roll number, then by name — you expect students with the same name to remain in roll-number order.

Which of our sorts are stable? #

We tested each algorithm on thousands of random lists with repeated keys:

Lecture point — making merge sort stable. "Do not allow elements from the right to overtake elements on the left": while merging, prefer the left list when breaking ties. In code, change if A[i] < B[j]: to if A[i] <= B[j]:.

Tried it ourselves on the table above (sorting by name):

• Quicksort gave: Asha 103, Asha 101, Meena, Ravi 105, Ravi 102 — order flipped.
• Merge sort with <= gave: Asha 101, Asha 103, Meena, Ravi 102, Ravi 105 — order kept.

Other criteria — minimizing data movement #

Imagine every item is a heavy carton. Comparing two cartons (reading their labels) is easy; moving them is hard work. Then we want a sort that makes few moves.

So "best" depends on what is expensive: comparing or moving.

Which sorting algorithm is best? #

There is no single winner:

• Quicksort is often the algorithm of choice, despite its O(n²) worst case.
• Merge sort is typically used for external sorting: when the data (for example, a huge database table) is too large to fit in memory. Parts are read from the disk, sorted, and merged back — merging works well when reading data in order.
• Heapsort is another O(n log n) algorithm (we will meet heaps later in the course).

Hybrid sorting — quicksort + insertion sort #

Divide and conquer is great for large n. But for a tiny list, all the recursive calls and partitioning cost more than they save. For small n, the simple insertion sort is actually faster.

Hybrid strategy:

• Use divide and conquer (quicksort or merge sort) while the part is large.
• When a part becomes small (for example, n < 16), switch to insertion sort.

import random

def insertion_sort_range(L, l, r):        # sort L[l:r] in place
    for i in range(l+1, r):
        j = i
        while j > l and L[j] < L[j-1]:
            (L[j], L[j-1]) = (L[j-1], L[j])
            j = j - 1

def partition(L, l, r):                   # random pivot, returns its final position
    p = random.randrange(l, r)
    (L[l], L[p]) = (L[p], L[l])
    (pivot, lower, upper) = (L[l], l+1, l+1)
    for i in range(l+1, r):
        if L[i] > pivot:
            upper = upper + 1
        else:
            (L[i], L[lower]) = (L[lower], L[i])
            (lower, upper) = (lower+1, upper+1)
    (L[l], L[lower-1]) = (L[lower-1], L[l])
    return lower - 1

def hybrid_sort(L, l, r):
    if r - l < 16:                        # small part: insertion sort
        insertion_sort_range(L, l, r)
        return L
    m = partition(L, l, r)                # large part: quicksort step
    hybrid_sort(L, l, m)
    hybrid_sort(L, m+1, r)
    return L

Note j > l (not j > 0): insertion sort here works only inside the part L[l:r], so it must stop at position l.

Tried it ourselves: sorting 2,00,000 random numbers, plain random-pivot quicksort took about 0.45 s; the hybrid (insertion sort below 16) took about 0.36 s — about 20% faster, from one small change.

Real-world example: Python's built-in sorted() uses Timsort, which is exactly this kind of hybrid — merge sort for large runs, insertion sort for small pieces — and it is stable.

In one line: A stable sort keeps equal items in their old order (insertion sort and merge sort with <= are stable; selection sort and quicksort are not); real libraries use hybrids that switch to insertion sort for small parts.

Exam words: stable sort, sort key, records/tuples, prefer left on ties (<=), data movement, external sorting, heapsort, hybrid sort, switch to insertion sort for n < 16, Timsort.

Quick check #