Skip to content
Tutorials Center
My learning

Topics

Lesson 86 of 225 ยท Sorting

Sorting in Libraries - qsort, std::sort, Arrays.sort and sorted()

What the sort functions of C, C++, Java, Python, JavaScript, Go and Rust really do: algorithms, stability, comparator rules and the bugs that bad comparators cause.

You have now built bubble, insertion, merge, quick, heap, counting and radix sort. In real projects you will write almost none of them. You will call a library function: qsort in C, std::sort in C++, Arrays.sort in Java, sorted() in Python. All of them promise to sort, but they differ in the things that bite you later: is it stable, what does it do when the comparison function is wrong, how many times does it call your key function, and how fast is it on data that is already almost sorted?

This lesson is a tour of those differences. The examples are in Python, because that is the language of this course, but the facts and the pitfalls apply to every language in the table. Library internals change between versions, so treat the algorithm names as "what you will typically find", and the guarantees (stable or not, complexity) as what you may rely on.

What the libraries promise

Language and function Typical algorithm Stable? Worst case
C: qsort not specified; often introsort or merge sort not guaranteed not specified
C++: std::sort introsort (quick + heap + insertion) no O(n log n)
C++: std::stable_sort merge sort with a buffer yes O(n log n) with enough memory
Java: Arrays.sort(int[]) dual-pivot quicksort n/a (primitives) O(n log n) in current JDKs
Java: Arrays.sort(Object[]), List.sort TimSort yes O(n log n)
Python: sorted, list.sort Timsort yes O(n log n)
JavaScript: Array.prototype.sort Timsort in V8 yes (required since ES2019) O(n log n) in practice
Go: sort.Slice, slices.Sort pattern-defeating quicksort no (sort.SliceStable is) O(n log n)
Rust: slice::sort / sort_unstable merge-based hybrid / quicksort-based hybrid yes / no O(n log n)

A few things to notice.

  • The C standard promises almost nothing. qsort has no stability guarantee, no complexity guarantee, and no named algorithm. Different C libraries behave differently, and the same library can change between releases. Never write code that depends on how qsort orders ties.
  • C++ splits the job in two. std::sort is the fast unstable one; std::stable_sort keeps ties in order and may use extra memory.
  • Java splits by type. Primitives have no identity, so stability is meaningless and a fast quicksort is used. Objects need stability (sort by city, then by name must work), so they get TimSort, a merge-based sort.
  • Timsort is everywhere in the managed languages. Python invented it, Java and V8 adopted it. It is a merge sort that finds the natural runs in your data first (see Shell sort, Timsort and hybrid sorts).

How fast on already-sorted data?

Textbook quicksort and heap sort do the same work whatever the input looks like. Timsort does not: it notices runs that are already in order and merges those. The next example counts how many times < is called for different input shapes.

Python Counting the comparisons Timsort makes

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Sorted and reversed input take just n - 1 comparisons (a reversed run is detected and flipped in place). Ten sorted runs take about a third of the random case. Random data needs roughly n log2 n minus a little, close to the theoretical minimum. A C++ std::sort does not have this adaptive behaviour: it is tuned for speed on random data, not for the "mostly sorted" case that real data often is.

Stability and the key function

Stability matters whenever you sort the same data twice (by city, then by name), or when equal items carry extra information. The example below shows that Python's sorted keeps ties in input order, that the key function is called once per item (not once per comparison), and how stable passes let you sort by several criteria.

Python Stable sorting, key calls and multi-pass sorting

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Because the key runs once per item, an expensive key (parsing a date, lowercasing a long string) costs n calls instead of about n log n. This is also why a key= function is almost always better than a comparison function: it is faster and it cannot be inconsistent.

Now see what an unstable sort does to the same idea. Selection sort swaps items across long distances, so equal items can change places.

Python An unstable sort scrambles ties

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Hearts came before clubs in the input, and sorted() keeps that order. The selection sort swapped the first card with the last one, so the two fives ended up the other way round. This is exactly what you risk when a library's sort is unstable.

Comparator pitfalls

Languages that sort with a comparison function (a function that returns negative, zero or positive) let you make mistakes the compiler cannot see. A library sort assumes your comparison is a proper strict weak ordering: consistent, transitive, and the same every time you ask. When it is not, the result is not just a wrong order. Depending on the library you can get an exception (Java's "Comparison method violates its general contract!"), an infinite loop, an out-of-bounds read (a known danger in C++ and C when the comparison is inconsistent), or a panic (Rust).

Three classic mistakes:

  1. Subtraction as comparison. Writing return a - b; works until the difference overflows a 32-bit integer.
  2. An inconsistent rule. For example "rock beats scissors beats paper beats rock". There is no order to find.
  3. NaN. A floating-point NaN is neither smaller, bigger nor equal to anything, so any comparison with it breaks the assumptions.

The next example reproduces all three. The 32-bit overflow is simulated by hand, because Python integers never overflow. We also add a fourth classic: mixing types.

Python Comparator mistakes, reproduced

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

The three-word sort returns different answers for different input orders: the sort has nothing to be correct about. With NaN, the "sorted" lists are not sorted at all, and the result depends on where the NaN started. And the last two lines show why [10, 9, 1, 100].sort() in JavaScript, which compares items as text unless you pass a comparator, famously gives [1, 10, 100, 9].

When a sort misbehaves, test the comparator first. A comparator must return the same answer every time, must satisfy "if a < b and b < c then a < c", and must treat equal items as equal in both directions. Prefer comparing with < on a precomputed key, or Integer.compare / std::cmp / Ordering helpers, over hand-written arithmetic.

Choosing in practice

  • Default to the language's normal sort. It is faster and better tested than anything you will write.
  • Need ties to stay in order? Use a stable one (sorted, Arrays.sort on objects, std::stable_sort, sort.SliceStable). If your language's fast sort is unstable, you can force stability by adding the original index as a final tiebreaker.
  • Sort by a derived value? Use a key (or the "decorate, sort, undecorate" idea) so the value is computed once per item.
  • Many repeated sorts of small, almost sorted data? An adaptive sort (Timsort) wins. A plain unstable quicksort will not take advantage of the order.
  • Small integer keys in a known range? A counting or radix sort beats any comparison sort.
  • Only the top k? Do not sort at all: use a heap (heapq.nsmallest) or a selection algorithm.

Common mistakes

  • Relying on the order of ties from an unstable sort (qsort, std::sort, slices.Sort).
  • Writing comparators as a - b on integers or floats.
  • Mutating the list while a sort is running, or sorting data whose comparison depends on changing state.
  • Forgetting that JavaScript's default sort() compares as strings.
  • Sorting with list.sort() and then using its return value, which is None.

Check your understanding

Quick check ยท 5 questions

of 5 answered You scored / 5 ยท perfect!

  1. 1. Which guarantee does the C standard give for qsort?

    The standard only requires that the array ends up ordered according to the comparison. Different C libraries use different algorithms, so never rely on how ties are ordered.
  2. 2. Why does Python call the key function once per item instead of once per comparison?

    sorted() builds a list of keys first and then compares those keys. An expensive key function therefore costs n calls, not about n log n.
  3. 3. What is wrong with the comparator 'return a - b' for 32-bit integers?

    With a large positive a and a large negative b, a - b exceeds the 32-bit range and wraps to a negative number, so the sort believes a is smaller than b.
  4. 4. How many comparisons does Timsort need for a list that is already sorted, in the best case?

    Timsort detects that the whole list is one ascending run, which takes n - 1 comparisons, and then has nothing to merge.
  5. 5. You need to sort records by city and keep records of the same city in their original order. Which tool fits?

    Only a stable sort guarantees that records with equal keys keep their input order.

Summary

  • Library sorts are heavily tuned hybrids: Timsort in Python, Java objects and V8; introsort-style sorts in C++; pattern-defeating quicksort in Go; a stable merge-based sort and an unstable quicksort-based one in Rust.
  • Know the guarantee, not just the name: qsort promises no stability, std::sort is unstable, std::stable_sort, sorted() and Arrays.sort on objects are stable.
  • Timsort is adaptive: sorted input costs n - 1 comparisons and partly ordered data is cheaper than random data.
  • A key function runs once per item and cannot be inconsistent; a hand-written comparator can overflow, break transitivity, or choke on NaN.
  • A broken comparator can cause wrong results, exceptions, or worse, depending on the language.

Next: Sorting Problems and Applications