Sorting: Keys, Numeric Order and Stability

Part I · Module 13 · Chapter 13.3 · Sorting: Keys, Numeric Order and Stability

Chapter 13.2 narrowed a stream and left the rows where they were. This chapter moves them.

1. The Default

$ sort names.txt
alpha
bravo
charlie

With no options, sort orders lines as text, comparing them character by character from the left.

That is the right default for words. It is the wrong default for numbers, and the next section is the most important thing in the chapter.

2. The Trap

$ cat nums.txt
2
10
9
100

$ sort nums.txt
10
100
2
9

10 and 100 come before 2. Not a bug — sort compared text, and the character 1 sorts before 2, so anything starting with 1 precedes anything starting with 2 regardless of length.

$ sort -n nums.txt
2
9
10
100

-n compares numerically.

Here it is doing real damage. Sorting a results file by cycle count:

$ tail -n +2 results.csv | sort -t, -k4
alu,7,PASS,1200
uart,5,PASS,2300
fifo,9,FAIL,340
alu,11,FAIL,560
cache,3,PASS,98000

Read the last column: 1200, 2300, 340, 560, 98000. That is not sorted by cycles in any sense a person means, and it does not announce itself — the rows are in an order, the table looks tidy, and 98000 being last is exactly what you expected, so nothing prompts you to check.

$ tail -n +2 results.csv | sort -t, -k4 -n
fifo,9,FAIL,340
alu,11,FAIL,560
alu,7,PASS,1200
uart,5,PASS,2300
cache,3,PASS,98000

3. Sorting by a Field

sort -t, -k3 results.csv        # by field 3

-t sets the separator and -k selects the key. The separator defaults to a run of whitespace, matching awk rather than cut (Chapter 13.1).

The -k syntax looks simple and has a wrinkle that matters.

-k2 means "from field 2 to the end of the line"

$ cat k2.txt
z 2 a
a 2 b
m 1 c

$ sort -k2 k2.txt
m 1 c
z 2 a
a 2 b

$ sort -k2,2 k2.txt
m 1 c
a 2 b
z 2 a

Different answers. Both put m 1 c first, and then they disagree.

• -k2 means from the start of field 2 to the end of the line, so the keys are 2 a and 2 b. Those differ, and a sorts first — so the z line wins.
• -k2,2 means field 2 only. Both keys are 2, a tie, so sort falls back to comparing whole lines — and a 2 b sorts before z 2 a.

4. Reverse, Unique and Stability

$ sort -rn nums.txt
100
10
9
2

-r reverses. sort -rn — numeric, descending — is the single most common combination in the whole toolkit, because it is the last stage of every "what is most frequent" pipeline.

$ printf '3\n1\n3\n2\n' | sort -u
1
2
3

-u removes duplicates while sorting, doing in one process what sort | uniq does in two (Chapter 12.8 — fewer stages, fewer statuses).

A caution: with a key, -u means unique by that key, not unique lines.

sort -t, -k1,1 -u results.csv     # one line per test name, others discarded

That is occasionally exactly what you want and occasionally a silent loss of data.

Stability

$ sort -k2,2 -s k2.txt
m 1 c
z 2 a
a 2 b

-s makes the sort stable: lines with equal keys keep their original relative order instead of being resolved by the whole-line fallback. Compare with §3, where -k2,2 put a 2 b first.

Stability matters when you sort twice to get a two-level ordering, which is sometimes clearer than a multi-key sort:

sort -k1,1 file | sort -k2,2 -s     # by field 2, ties broken by field 1

Without -s the second sort discards the first one's work.

5. The Locale Changes the Answer

$ cat case.txt
b
A
a
B

$ LC_ALL=C sort case.txt
A
B
a
b

$ LC_ALL=en_US.UTF-8 sort case.txt
a
A
b
B

Two different, equally correct answers. LC_ALL=C compares by character code, so all uppercase precedes all lowercase. A human-language locale uses dictionary order, where a and A sit together.

This matters for three reasons:

• A script can produce different output on two machines whose locales differ, with nothing in the script to explain it.
• Case-sensitive comparisons downstream break. comm and join both require their inputs sorted the same way, and "sorted" is locale-dependent.
• C is faster — a byte comparison rather than a collation lookup.

6. Other Flags Worth Knowing

Two of those are more useful than they look.

-c is a cheap assertion:

$ sort -c names.txt && echo "already sorted"

Useful before join or comm, which produce wrong answers rather than errors on unsorted input (Chapter 13.8).

-o is the one safe in-place sort:

sort -o data.txt data.txt        # safe — documented to work
sort data.txt > data.txt         # EMPTIES the file

Chapter 12.2 showed why the second destroys the file: the shell opens it for writing before sort reads a byte. sort -o reads its input fully before opening the output, and is documented to support exactly this case.

It is tool-specific. grep -o means something entirely different, and most tools have no equivalent. The general pattern remains a temporary file and && mv.

7. Performance

sort must see every line before emitting the first, so it is the one tool in this module that genuinely buffers (Chapter 12.5). On a file larger than memory it spills to temporary files automatically and still works — slowly.

Two practical consequences:

Filter before sorting, as Chapter 12.5 argued:

grep ERROR enormous.log | sort        # sorts a few hundred lines
sort enormous.log | grep ERROR        # sorts four gigabytes first

sort -u beats sort | uniq — one process, and it discards duplicates as it goes rather than writing them out and reading them back.

If you are sorting something genuinely large, -S sets the memory buffer and --parallel sets the thread count on GNU sort; both are absent from the BSD version.

8. In Practice

# the most common pipeline ending in the whole toolkit
sort | uniq -c | sort -rn | head -10

That shape — group, count, rank, truncate — answers "what is most common" for errors, test failures, users, file extensions, anything. Chapter 13.4 is the middle of it.

A realistic sort:

# slowest tests first, with a second key to break ties predictably
tail -n +2 results.csv | sort -t, -k4,4rn -k1,1

-k4,4rn is three modifiers on one key: field 4 only, reversed, numeric. The second key makes the output deterministic when two tests took the same number of cycles — worth doing whenever the output will be compared between runs.

# directories by size, largest first
du -sh */ | sort -hr | head -10

# a sorted file intended for join
LC_ALL=C sort -t, -k1,1 -o owners.sorted.csv owners.csv

Practice

mkdir -p /tmp/srt && cd /tmp/srt
printf '2\n10\n9\n100\n' > nums.txt
printf 'z 2 a\na 2 b\nm 1 c\n' > k2.txt
printf 'b\nA\na\nB\n' > case.txt
cat > results.csv <<'EOF'
test,seed,result,cycles
alu,7,PASS,1200
fifo,9,FAIL,340
cache,3,PASS,98000
alu,11,FAIL,560
uart,5,PASS,2300
EOF

1 — Spring the trap.

sort    nums.txt | tr '\n' ' '; echo
sort -n nums.txt | tr '\n' ' '; echo

2 — See it on real data.

tail -n +2 results.csv | sort -t, -k4
echo "---"
tail -n +2 results.csv | sort -t, -k4 -n

Read the last column of each.

3 — Make -k2 and -k2,2 disagree.

sort -k2   k2.txt
echo "---"
sort -k2,2 k2.txt

Explain the difference before reading §3 again.

4 — Add a second key.

tail -n +2 results.csv | sort -t, -k3,3 -k4,4n

5 — Try stability.

sort -k2,2    k2.txt
echo "---"
sort -k2,2 -s k2.txt

6 — Compare locales.

LC_ALL=C           sort case.txt | tr '\n' ' '; echo
LC_ALL=en_US.UTF-8 sort case.txt | tr '\n' ' '; echo

7 — Check instead of sorting.

sort -c nums.txt && echo "sorted" || echo "not sorted"
sort -n nums.txt | sort -c -n && echo "now sorted"

8 — Sort a file in place, two ways.

cp nums.txt a.txt; sort -n -o a.txt a.txt; cat a.txt | tr '\n' ' '; echo
cp nums.txt b.txt; sort -n b.txt > b.txt; echo "b.txt is now $(wc -c < b.txt) bytes"

9 — Human sizes.

printf '2K\n1M\n500\n3G\n' | sort    | tr '\n' ' '; echo
printf '2K\n1M\n500\n3G\n' | sort -h | tr '\n' ' '; echo

10 — Clean up. cd /tmp && rm -rf /tmp/srt

Check Your Understanding

1. sort puts 100 before 2. Is it broken?

2. Why is a lexical sort of numbers more dangerous than an error would be?

3. What is the difference between -k2 and -k2,2?

4. sort -n -k3,3 -k4,4 — which keys are numeric?

5. Why might the same script give a different sort order on two machines?

6. sort data.txt > data.txt empties the file. What is the safe form, and why is it not a general pattern?

9. Remember

• The default is a text comparison, which is right for words and wrong for numbers.
• -n for numbers, always. A lexical sort of digits is ordered, complete and wrong, with no warning.
• -h for human sizes, -V for versions, -g for scientific notation.
• -t sets the separator, -k the key. The separator defaults to whitespace, like awk.
• -kN means field N to the end of the line. Write -kN,N to mean one field.
• Modifiers attach to a key: -k4,4rn is field 4, reversed, numeric.
• -r reverses, and sort -rn is the most common combination in the toolkit.
• -u removes duplicates in one process, but with a key it means unique by that key.
• -s makes the sort stable, which is what two-pass sorting requires.
• The locale changes the answer. Use LC_ALL=C for anything reproducible or machine-consumed.
• -c checks sortedness cheaply — worth doing before join or comm.
• sort -o f f is the one safe in-place sort, and it is tool-specific.
• sort buffers everything, so filter before sorting and prefer sort -u to sort | uniq.
• A numeric field sorted as text ranks 100 above 20. Chapter 24.6 §4 measures it, and why a mis-sorted table is worse than none.
• A filelist must be sorted deliberately, with the locale pinned — Chapter 26.4 measures sort -u f > f leaving zero bytes, and find's order being stable but name-hashed.

Sorting brings identical lines together. The next chapter is the tool that does something with them — and the one that fails silently whenever this chapter's step is skipped.