---
title: 'Sorting, Deduplication, and Joining'
source: 'https://academia.sh/en/courses/shell-programming/sorting-deduplication-and-joining'
course: 'Shell Programming'
language: en
updated: '2026-08-17T18:10:03+00:00'
license: 'CC BY-SA 4.0'
---

# Sorting, Deduplication, and Joining

Sorting by key, the effect of the locale on sort order, deduplication that requires adjacency, and set operations over sorted streams.

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.

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

```
10
100
2
9
```

```sh
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.

```sh
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.

```sh
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.

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

```
c 0
a 1
b 1
```

```sh
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.

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

```
A
B
a
b
```

```sh
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.**

```sh
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:

```sh
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 |

```sh
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:

```sh
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
```

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

```
/login
```

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

```
/old-page
```

```sh
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:

```sh
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:

```sh
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.

```sh
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:

```sh
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:

```sh
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.