Sorting and deduplicating a list without surprises

Sorting and deduplicating look like the two simplest things you can do to a list, which is why the results are so often quietly wrong. Both rest on a comparison, and there is no single answer to what makes two lines equal or one line come first.

Lexicographic order is not numeric order

The default comparison for text walks two strings one character at a time, compares code points, and stops at the first difference. Nothing in it knows what a number is.

input:   img1.png, img2.png, img10.png
sorted:  img1.png, img10.png, img2.png

img10.png lands second because at the fourth character 1 (U+0031) is lower than 2 (U+0032), and the comparison ends there. The same rule puts version 1.10 before 1.9, and lists a folder of screenshots out of the order they were taken.

Numeric comparison also fixes negatives: lexicographically, -10 falls between -1 and -2, because a minus sign is just another character with a code point.

Uppercase before lowercase, and other code point surprises

In ASCII, capitals occupy 65 to 90 and lowercase letters 97 to 122, so every capital sorts before every lowercase letter.

Digits sit below all letters, the space (32) below every printable character, and an empty line below that, so an ascending sort collects blank and space-prefixed lines at the very top and a descending sort collects them at the bottom.

Trailing whitespace is the invisible version of the same problem: apple and apple sort next to each other and look like a duplicate that refuses to be removed. The non-breaking space (U+00A0) is worse, drawn identically to a normal space but sorting above every letter, as is the carriage return left behind when a Windows file is split on newlines alone. If two lines look identical and still will not collapse, check for hidden characters.

The same list sorts differently in two countries

Code point order also puts every accented character after every unaccented one. Zürich sorts after Zzz, and Ärger after zebra. No language orders its own alphabet that way. Locale-aware collation compares by language rules instead, and those rules disagree with each other.

In JavaScript this lives in Intl.Collator:

const words = ["Zebra", "Ärger", "Apfel"];

words.sort(new Intl.Collator("de").compare);
// Apfel, Ärger, Zebra

words.sort(new Intl.Collator("sv").compare);
// Apfel, Zebra, Ärger

The same object covers the earlier problems. { numeric: true } compares digit runs as numbers, which is natural order, and sensitivity sets what counts as a difference: "base" ignores case and accents, "accent" ignores case only, "case" ignores accents only. Omitting the locale uses whatever the machine is set to, which is how the same code returns two different orders on two laptops. Name the locale when output must match everywhere.

Which duplicates count as duplicates

Deduplication is only as well defined as the equality test behind it. Take five lines that all render as the word cafe with an acute accent:

Four reasonable rules give four different answers:

None of them is wrong; they answer different questions. Normalisation matters more than it looks, because text from macOS file names tends to arrive decomposed (NFD) and text from Windows and web forms composed (NFC), so a list pasted from two sources picks up invisible twins. NFKC goes further, folding compatibility characters such as the fi ligature into their plain equivalents.

The first occurrence conventionally wins, so if the untidy copy was pasted first, it survives. And removing duplicates is a different request from finding unique items: Remove Duplicate Lines leaves one of each, while the unique set in List Frequency is the smaller group of items appearing exactly once.

Stability, and sorting by two keys

A stable sort guarantees that entries the comparator calls equal keep the order they had in the input. That is what makes multi-key sorting by repeated passes work: sort by the least important key first, then the most important. Sorting by name and then by department gives departments in order, with names ordered inside each one. An unstable sort undoes the first pass while doing the second, and the result looks almost right, which is worse than looking wrong.

Reversing carries the same catch, because flipping a sorted list also reverses each tied group. Use Reverse List when turning the whole order around is what you want, not as a shortcut to a descending sort.

Implementations differ. JavaScript's Array.prototype.sort has only been required to be stable since ES2019; before that V8 used an unstable quicksort above a small array size, so the same code behaved differently on ten items and on ten thousand. Python's sorted is stable, and GNU sort is not unless given -s.

Shuffling is not a kind of sorting

The one-line shuffle, list.sort(() => Math.random() - 0.5), is biased. A sort assumes its comparator describes a consistent order, and asks about only the subset of pairs its algorithm needs. A comparator that rolls a fresh number every call breaks that assumption, so the result depends on the algorithm and the array length: items tend to stay near where they started, and some permutations turn up far more often than others.

A correct shuffle uses Fisher-Yates, walking from the end and swapping each item with a uniformly chosen item at or before it:

for (let i = list.length - 1; i > 0; i--) {
  const j = Math.floor(Math.random() * (i + 1));
  [list[i], list[j]] = [list[j], list[i]];
}

The common broken variant uses Math.random() * list.length inside the loop, drawing from the whole array every time. That gives n to the power n equally likely sequences of draws, which does not divide evenly by the n factorial orderings, so some orderings come up more often.

Randomness and sorting can be combined correctly by giving each item one random key up front and sorting by that key, because the comparator then stays consistent. The failure is rolling the die inside the comparison.

The order the steps go in

Most list problems come from doing the right operations in the wrong sequence.

1. Unwrap first. A list copied out of code arrives as "apple",; the quotes and comma are part of the string, so it never matches apple. Unwrap List Items strips them.
2. Trim and normalise, so that equality means what you think it means.
3. Deduplicate, with the matching rule chosen deliberately rather than taken as a default.
4. Sort. Sort Lines covers text, numeric, length and random order; add a locale for accented data.
5. Reshape last. Group List Items cuts the result into fixed-size batches for a per-request limit, and Rotate List shifts everything along without changing the internal order.

Deduplicating before trimming leaves near-duplicates behind, and sorting before deduplicating just sorts rows that are about to be thrown away.