Sorting, Deduplication, and Joining

In previous lessons, every count ended with sort, but the command itself was never explained. Sorting is the second most frequently called tool in shell text processing, and it deserves a lesson of its own for two reasons: its options change the result entirely, and the three tools alongside it — deduplication, comparison, joining — depend on their input being sorted.

The Algorithms course defined sorting’s cost and the stability criterion. This lesson ties those concepts to a command’s options.

Lexicographic Order and Numeric Order

The default comparison is lexicographic order: values are compared character by character.

printf '10\n9\n100\n2\n' | sort

10
100
2
9

printf '10\n9\n100\n2\n' | sort -n

2
9
10
100

In lexicographic order, 10 comes before 9 because its first character, 1, is smaller than 9. Wherever numbers are sorted, -n is required; forgetting it is the most common silent bug in reports.

-r reverses the order. -n -r together is the standard spelling for sorting from largest to smallest.

Key Definition

The -k option states which field the comparison is done over. Its form is -k start,end, and writing the end is mandatory: -k2 means “from the second field to the end of the line,” -k2,2 selects only the second field.

awk '{ print $7, $10 }' access.log | sort -k2,2n | head -3

/login 0
/old-page 0
/static/style.css 0

Numeric mode can also be attached to the key: the form -k2,2n applies only to that key. When more than one -k is given, the keys apply in sequence, moving to the next key on a tie.

-t sets the delimiter. The default delimiter differs from the field-based tool’s: the point where a run of whitespace transitions into non-whitespace counts as the separator.

printf 'c:3\na:1\nb:2\n' | sort -t: -k2,2n

a:1
b:2
c:3

Stability

Sorting is not stable by default: the relative order of lines with equal keys is not preserved. On a tie, the entire line is compared as a last resort.

printf 'b 1\na 1\nc 0\n' | sort -k2,2n

c 0
a 1
b 1

printf 'b 1\na 1\nc 0\n' | sort -s -k2,2n

c 0
b 1
a 1

The -s option turns off the last-resort comparison and preserves the input order. In multi-key sorts — first by city, then stably by date — the stability requirement shown in the Algorithms course is met with this option.

Locale

The comparison order depends on the runtime environment’s locale.

printf 'a\nB\nb\nA\n' | LC_ALL=C sort

A
B
a
b

printf 'a\nB\nb\nA\n' | LC_ALL=en_US.UTF-8 sort

a
A
b
B

The first order sorts by byte value, the second on a letter basis. Both are correct; the problem is that which one applies depends on the environment the script runs in.

This is the primary source of unreproducible results in scripts. The same script gives differently sorted output on two machines; a check that compares one output against another fails despite there being no real difference.

Rule: if a script does sorting, the locale is fixed explicitly.

LC_ALL=C sort ...

LC_ALL=C selects byte order; it is fast, predictable, and identical across machines. If a letter-based order is wanted for a human reader, the locale must still be written explicitly — it must not be left ambiguous.

Because operations such as sort -u and uniq also take their definition of “equality” from the locale, they can produce a different number of lines under different settings. Fixing the locale is therefore not just a matter of order.

Deduplication

uniq reduces adjacent repeated lines to one. It does not behave as expected on unsorted input:

printf 'a\nb\na\n' | uniq -c
printf 'a\nb\na\n' | sort | uniq -c

   1 a
   1 b
   1 a
   2 a
   1 b

Nothing was merged in the first call, because the repeated a lines were not adjacent. This is the justification for the sort | uniq -c pattern used since the course’s first topic.

The options answer different questions:

Option	Output
-c	repeat count in front of each line
-d	only lines that occur more than once
-u	only lines that occur exactly once
-i	case-insensitive comparison

printf 'a\nb\nb\nc\n' | uniq -u

a
c

sort -u and sort | uniq give the same result, but sort -u is cheaper: no separate process is created. If uniq -c is needed, two steps are required, because sort -u does not count.

Set Operations

comm compares two sorted files and produces three columns: lines only in the first, only in the second, in both. The -1, -2, -3 options suppress the corresponding column.

The requested paths in the log’s first and last fifteen lines are compared below. Both files are prepared deduplicated and sorted with the same locale:

export LC_ALL=C
head -15 access.log | cut -d' ' -f7 | sort -u > yesterday.txt
tail -15 access.log | cut -d' ' -f7 | sort -u > today.txt

comm -23 yesterday.txt today.txt      # only in the first

/login

comm -13 yesterday.txt today.txt      # only in the second

/old-page

comm -12 yesterday.txt today.txt      # common to both

/api/data
/index.html
/missing.html
/panel
/product/12
/product/45
/secret
/static/style.css

The three calls give, in order, the set difference, the reverse difference, and the intersection. Both files must be sorted, and sorted with the same locale; otherwise comm warns, or silently produces a wrong result.

This tool is the direct way to compare two logs: which paths were requested only in this period, which clients disappeared, which error codes newly appeared.

join merges two sorted files over a common key field; it is the text-based counterpart of the join operation in relational databases.

The per-path request count and total bytes are produced in two separate files and sorted by key:

awk '{ count[$7]++ }     END { for (y in count) print y, count[y] }' access.log | sort -k1,1 > count.txt
awk '{ bytes[$7] += $10 } END { for (y in bytes)  print y, bytes[y]  }' access.log | sort -k1,1 > size.txt
join count.txt size.txt | head -5

/api/data 6 7236
/index.html 4 20480
/login 1 0
/missing.html 4 2048
/old-page 1 0

By default, the first field of both files is taken as the key; the -1 and -2 options change the field number, -t sets the delimiter. The inputs must be sorted by the key field — not by the entire line. This distinction is the source of the most common mistake in using join.

Deterministic Sorting

In count output, the order of lines with an equal count depends on the last-resort comparison and the locale. This can prevent the report from coming out the same on every run:

cut -d' ' -f7 access.log | sort | uniq -c | sort -rn | head -5

   6 /api/data
   4 /missing.html
   4 /index.html
   3 /static/style.css
   3 /product/45

When a secondary key is given explicitly, the result becomes deterministic: descending by count first, ascending by name on a tie.

cut -d' ' -f7 access.log \
  | LC_ALL=C sort | uniq -c | LC_ALL=C sort -k1,1nr -k2,2 | head -5

   6 /api/data
   4 /index.html
   4 /missing.html
   3 /panel
   3 /product/12

Lines with an equal count are now in alphabetical order. This spelling should be used in any script whose output will be tested or compared between two runs.

Applying to the Script

report.sh receives two changes. First, the locale of every sort is fixed and a secondary key is given:

export LC_ALL=C

top_n() {                       # top_n FIELD FILE COUNT
  local field="$1" file="$2" count="$3"
  cut -d' ' -f"$field" "$file" | sort | uniq -c | sort -k1,1nr -k2,2 | head -"$count"
}

export LC_ALL=C is placed at the top of the script, so every tool it calls uses the same order. This makes the script’s output independent of the environment it runs in.

Second, an option is added that compares two logs:

compare() {                     # compare OLD NEW
  local old="$1" new="$2"
  cut -d' ' -f7 "$old" | sort -u > "$tmp_dir/old"
  cut -d' ' -f7 "$new" | sort -u > "$tmp_dir/new"
  section "Paths seen only in the new log"
  comm -13 "$tmp_dir/old" "$tmp_dir/new"
}

This function writes to temporary files and does not clean them up. This gap will be closed with mktemp and traps in the Robust Script Writing topic.

Summary

• The default comparison is lexicographic order; -n is mandatory on numeric data.
• -k start,end bounds the key; if the end is not written, the key extends to the end of the line.
• Sorting is not stable by default; -s turns off the last-resort comparison.
• The comparison order depends on the locale; in scripts it must be fixed with LC_ALL=C.
• uniq merges only adjacent repeats; this is why the sort | uniq -c pattern is inseparable.
• comm and join require sorted input; the first performs set operations, the second joins over a key.

Next Step

Every tool in this topic worked at the line level. Cutting at the column level, pasting two files side by side, and splitting a large log into pieces requires a separate family of tools. The next lesson takes up that family and closes out the text processing topic with a selection criterion that decides which job belongs to which tool.