How Linux sort Implements Numeric Sorting

This article explores how the Linux operating system, primarily via GNU Coreutils, implements the -n (--numeric-sort) flag in the standard sort utility. It details the underlying algorithmic logic, internal string-parsing routines, and design choices that allow the system to compare numbers accurately and efficiently without encountering traditional integer overflow issues.

The GNU Coreutils Foundation

In the Linux operating system, the user-space sort utility is provided by GNU Coreutils. The source code, located in src/sort.c, defines the behavior of sorting algorithms and comparison flags. When you pass the -n or --numeric-sort option, sort bypasses standard lexicographical collating sequences (like those governed by LC_COLLATE) and redirects line comparisons to specialized numerical comparison routines.

String-Based Numerical Comparison

Unlike generic programming routines that parse strings into machine-native data types like 32-bit or 64-bit integers (atoi or strtol), the Linux sort -n implementation evaluates numbers primarily at the byte level through a function historically known as numcompare.

Converting strings directly into machine integers introduces two main limitations: potential arithmetic overflow when dealing with exceptionally large numbers, and performance overhead from repeated type conversions. To avoid this, sort processes the text directly as character sequences.

Step-by-Step Execution of numcompare

When two lines are evaluated under the numeric flag, the comparison algorithm executes the following sequence:

  1. Whitespace Truncation: The parser advances past any leading blank spaces (spaces and tabs) in both lines until it encounters the first non-whitespace character.
  2. Sign Evaluation: The routine checks for an optional leading sign (+ or -). If a minus sign is detected, a negative flag is stored for that operand. If one number is positive and the other negative, the comparison resolves immediately. If both are negative, the final comparison result is inverted.
  3. Leading Zero Suppression: Any leading zeros before the significant digits or decimal separator are skipped. This step aligns the significant figures of both numbers.
  4. Magnitude Comparison via Digit Counting: The function scans ahead to count the number of continuous decimal digits up to the radix point (decimal separator, which respects the current locale's LC_NUMERIC setting). If one number has more integer digits than the other, it is automatically declared larger (or smaller, if negative). This allows the tool to sort arbitrarily large numbers without buffer or integer limit constraints.
  5. Character-by-Character Comparison: If both numbers have the exact same count of integer digits, the function compares the digits one by one from left to right. The first pair of mismatched characters determines the greater value.
  6. Fractional Part Evaluation: If the integer parts are identical, the parser evaluates characters following the decimal point. It compares digits sequentially until a difference is found. If one fraction terminates before the other, the shorter sequence is conceptually padded with trailing zeros to evaluate which value is mathematically greater.

Non-Numeric Fallbacks and Tie-Breaking

If a string begins with non-numeric characters (or contains no digits after a sign), sort -n treats its numerical value as zero.

When two lines evaluate to identical numeric values (for example, 01 and 1), they are considered equal by the numeric comparison phase. If no other sorting criteria are specified and the -s (--stable) flag is not used, the utility executes a byte-level fallback comparison across the entire line to maintain a deterministic, predictable order.

Why Not Floating-Point Hardware?

Linux separates numeric sorting into -n (--numeric-sort) and -g (--general-numeric-sort). The -g flag relies on the C library's strtold function to convert strings into long double floating-point numbers, supporting scientific notation (e.g., 1e10).

However, -n avoids hardware floating-point operations entirely. By treating the numerical value as a character array with structural constraints, the -n implementation delivers significantly faster execution speeds and avoids the floating-point precision loss inherent to machine representations.