Unicode's collation algorithm (DUCET — Default Unicode Collation Element Table) is a 30,000+ line table that defines exactly how every Unicode character should sort relative to every other — and most software ignores it entirely, defaulting to code-point order that produces results that surprise users and break internationalization
The previous articles on this site covered sorting algorithms, file-number sort order ("file10 before file2"), natural sort vs lexicographic, and locale collation with Swedish Å. This article addresses stable vs unstable sorting — the algorithmic property that determines whether equal elements maintain their original relative order, and why it matters for practical data processing.
What stable sorting means and why it matters
A sorting algorithm is stable if elements with equal sort keys maintain their original relative order. An unstable sort may reorder equal elements arbitrarily.
Why this matters: composable multi-key sorting.
Suppose you want to sort a list of transactions first by date, then (within the same date) by amount:
Transaction A: 2024-01-15, £50
Transaction B: 2024-01-15, £100
Transaction C: 2024-01-10, £75
Transaction D: 2024-01-15, £50
Approach 1 (single multi-key sort): sort by (date, amount) simultaneously.
Approach 2 (stable sort composition):
- Sort by amount ascending (stable sort)
- Then sort by date ascending (stable sort)
After step 1: C(£75 on 10th), A(£50 on 15th), D(£50 on 15th), B(£100 on 15th) — wait, actually by amount: A(£50), D(£50), C(£75), B(£100)
After step 2 (stable sort by date): C(10th, £75), A(15th, £50), D(15th, £50), B(15th, £100)
Because the date sort was stable, the relative order of A, D, B from step 1 (amount order) is preserved within the same date — giving a result sorted by date, then by amount within each date.
With an unstable sort, step 2 might arbitrarily reorder A, D, B within the same date, losing the amount-ordering from step 1.
Stable vs unstable: which algorithms are which
Stable sorting algorithms:
- Merge sort: O(n log n), stable, additional O(n) memory
- Insertion sort: O(n²) worst case, stable, in-place, fast for small inputs
- Timsort: O(n log n) worst case, stable, hybrid merge/insertion sort — Python's default sort, Java's Arrays.sort for objects, JavaScript's Array.sort in modern engines
Unstable sorting algorithms:
- Quicksort: O(n log n) average, unstable, in-place — fastest in practice for random data
- Heapsort: O(n log n), unstable, in-place
- Shell sort: O(n log n) to O(n²), unstable
JavaScript's Array.sort(): was historically not required to be stable by the spec (and different browsers implemented it differently — Chrome used unstable quicksort, Firefox used stable merge sort). Since 2018, the ECMAScript spec was updated to require stable sorting, and all modern browsers comply. Code written before 2018 that relied on sort stability may have had browser-specific behavior.
Case sensitivity in sorting: the invisible difference
Text sorting with case sensitivity differences produces completely different orderings:
Case-sensitive (code point order):
Apple
Banana
apple
banana
(Capital letters have lower code points than lowercase in ASCII/Unicode)
Case-insensitive (folded before comparison):
apple (or Apple — whichever came first in the input)
Apple (or apple)
banana (or Banana)
Banana (or banana)
For user-facing lists: case-insensitive sorting is almost always preferred — alphabetical order that treats "apple" and "Apple" the same reflects how humans expect sorting to work.
For technical data: case-sensitive may be appropriate (file paths on case-sensitive filesystems, code identifiers in case-sensitive languages).
Numeric sorting in text fields: the collision between types
Numbers stored as text strings sort lexicographically — which produces "correct" results for numbers of equal digit length but wrong results for numbers of different lengths:
Lexicographic (string) sort:
1
10
100
2
20
3
Numeric (integer) sort:
1
2
3
10
20
100
This affects: version numbers, file names with numbers, IP addresses as strings, date strings in non-ISO formats, and any field that contains numbers but is stored/treated as text.
The natural sort problem (covered in the previous "file10 before file2" articles) is specifically this: "file2" and "file10" as strings sort lexicographically with file10 first (because "1" < "2" in character comparison, comparing character by character). Natural sort solves this by extracting and numerically comparing the numeric portions.
Reverse sort: what it does to equal elements
Reversing a sort order (ascending to descending) combined with a stable sort raises a subtle question: are equal elements reversed in their relative order, or maintained?
If the sort is stable and then reversed, equal elements will be in the reversed relative order from their original position (since reversing flips all positions, including equal ones).
Practical impact: if you want "sort descending by date, then ascending by amount within each date," you cannot simply reverse a stable ascending sort — you need either a multi-key sort with proper direction specification, or careful two-step stable sorting with specific direction handling.
How to use the Sort Lines tool on sadiqbd.com
- For lists with mixed case: use the case-insensitive option to get alphabetical order that treats "Apple" and "apple" as equivalent — case-sensitive sort produces the surprising capital-before-lowercase order
- For numbered lists: use numeric sort when numbers appear in the lines — this sorts by numeric value rather than lexicographically, giving the expected 1, 2, 3, 10, 20 order
- For reverse sorting: verify whether equal elements should maintain their original relative order or be reversed — if composing with a previous sort, stability matters
Frequently Asked Questions
Why does my spreadsheet sort "10" before "2" when sorting a column of numbers?
Because the column is stored as text, not as numbers. When a column is formatted as text (or contains values that Excel/Sheets decided to treat as text), sorting is lexicographic. To fix it: ensure the column is formatted as a number type, not text. In Excel: select the column, Format Cells → Number. In Google Sheets: Format → Number → Number. If the values have leading apostrophes or were imported as text, you may need to convert them using VALUE() formula or by using the "Text to Columns" feature to re-parse the values as numbers. Once the column is numeric type, sorting will correctly order 1, 2, 3, 10, 20 rather than 1, 10, 2, 20, 3.
Is the Sort Lines tool free? Yes — completely free, no sign-up required.
Try the Sort Lines tool free at sadiqbd.com — sort text lines alphabetically, numerically, by length, or randomly with case-insensitive and reverse options.
