Real-World Use

You will rarely implement a sorting algorithm at work. What matters is knowing which algorithm your language uses, whether it is stable, and how to pass comparators safely. This chapter covers the built-in sorts of major languages, common pitfalls, and tools that can replace a full sort.

Built-in sorts by language

Python's Timsort finds runs that are already sorted, extends short runs with binary insertion sort, and then merges runs. When one side keeps winning, galloping mode skips ahead with exponential search. That makes it very fast on sorted or nearly sorted data and on two sorted lists concatenated together. CPython 3.11 replaced the rule that decides the merge order with the Powersort policy, but stability and the O(n log n) worst case are unchanged. Java's object sort is a port of Python's Timsort.

The C++ standard does not prescribe an algorithm for std::sort; since C++11 it only requires O(n log n) comparisons. Major implementations such as libstdc++ use introsort: start with quicksort, switch to heapsort when recursion gets deeper than about 2 log n, and finish small ranges with insertion sort. When you need stability, use std::stable_sort.

When you do not need a full sort

If you only need part of the order, cheaper tools exist.

import heapq

scores = [72, 95, 88, 61, 99, 85, 90, 77]
print(heapq.nlargest(3, scores))   # [99, 95, 90]  O(n log k)
print(heapq.nsmallest(2, scores))  # [61, 72]

import bisect
ranked = sorted(scores)
bisect.insort(ranked, 93)          # insert while keeping the list sorted
print(ranked[bisect.bisect_left(ranked, 90):])  # 90 and above: [90, 93, 95, 99]

In C++, std::partial_sort sorts only the first k elements, and std::nth_element places the k-th element correctly and partitions around it in average O(n), which is ideal for medians and percentiles.

#include <algorithm>
#include <functional>
#include <iostream>
#include <vector>

int main() {
    std::vector<int> v{72, 95, 88, 61, 99, 85, 90, 77};
    std::nth_element(v.begin(), v.begin() + v.size() / 2, v.end());
    std::cout << "median-ish: " << v[v.size() / 2] << '\n';  // 88
    std::partial_sort(v.begin(), v.begin() + 3, v.end(), std::greater<int>());
    std::cout << v[0] << ' ' << v[1] << ' ' << v[2] << '\n';  // 99 95 90
}

Databases avoid sorting for ORDER BY when an index already provides the order, and fall back to external merge sort, sorting chunks to disk and merging them, when the result does not fit in memory. The Unix sort command handles huge log files the same way.

Common pitfalls

• JavaScript's default sort compares elements as strings: [10, 9, 1].sort() gives [1, 10, 9]. Always pass (a, b) => a - b for numbers.
• An inconsistent comparator (not transitive, or random) produces garbage, and in Java can throw IllegalArgumentException: Comparison method violates its general contract!.
• In Java, (a, b) -> a - b overflows for large values. Use Integer.compare or Comparator.comparingInt.
• NaN compares false against everything and corrupts the result. Filter it out or handle it in the key.
• Human-friendly string order is not code point order. For case, accents and language rules, use locale-aware comparison such as Intl.Collator or ICU.

import java.util.ArrayList;
import java.util.Comparator;
import java.util.List;

public class Ranking {
    record Player(String name, int score) {}

    public static void main(String[] args) {
        List<Player> players = new ArrayList<>(List.of(
            new Player("lee", 90), new Player("kim", 95), new Player("park", 90)));
        players.sort(Comparator.comparingInt(Player::score).reversed()
                .thenComparing(Player::name));
        System.out.println(players);  // kim 95, lee 90, park 90
    }
}

const nums = [10, 9, 1];
console.log([...nums].sort());                // [1, 10, 9] string comparison
console.log([...nums].sort((a, b) => a - b)); // [1, 9, 10]

const names = ["Émile", "zoe", "Adam"];
console.log([...names].sort(new Intl.Collator("fr").compare)); // ["Adam", "Émile", "zoe"]

Further reading

• Sorting Techniques (Python docs)
• CPython listsort.txt: Timsort design notes
• std::sort (cppreference)
• Arrays (Java SE 21 API)
• Array.prototype.sort() (MDN)
• VisuAlgo: sorting visualizations

Summary

• Knowing your built-in sort's algorithm and stability covers most practical needs.
• For top-k, medians and keeping data sorted, heaps, selection and binary search beat a full sort.
• Comparator consistency, numeric versus string comparison, NaN and locale rules cause most sorting bugs.