Skip to content

6.18 Sorting Records

Sort structured values by one or more fields while moving the full record, with attention to key extraction, stability, and multi-key ordering.

algorithms sorting records multi-key

Sorting records means sorting structured values by one or more fields. The record itself usually contains more information than the key used for ordering. The sorting algorithm must move the whole record while comparing only the selected fields.

Problem

You have records such as:

(name, department, salary, hired_at)

You want to sort them by a rule such as:

department ascending
salary descending
hired_at ascending

Solution

Define a key that represents the intended order.

key(record):
  return (
    record.department,
    -record.salary,
    record.hired_at
  )

Then sort records by that key.

sort(records, key = key)

The sorted order is lexicographic. First compare department. If departments are equal, compare salary in descending order. If salaries are equal, compare hired_at.

Example

Input:

[
  (Ana,  Eng, 120, 2021),
  (Bo,   Ops, 100, 2020),
  (Cy,   Eng, 140, 2022),
  (Dee,  Eng, 120, 2019)
]

Sort by department ascending, salary descending, hired year ascending:

[
  (Cy,   Eng, 140, 2022),
  (Dee,  Eng, 120, 2019),
  (Ana,  Eng, 120, 2021),
  (Bo,   Ops, 100, 2020)
]

Cy comes first among engineering records because salary 140 is highest. Dee comes before Ana because both have salary 120, and 2019 comes before 2021.

Comparator Form

The same rule can be written as a comparator.

compare(a, b):
  if a.department < b.department: return -1
  if a.department > b.department: return 1

  if a.salary > b.salary: return -1
  if a.salary < b.salary: return 1

  if a.hired_at < b.hired_at: return -1
  if a.hired_at > b.hired_at: return 1

  return 0

This form is explicit, but longer. The key-extraction form is usually easier to read and test.

Stability and Original Order

If the key does not include every field, multiple records may compare equal. A stable sort keeps equal-key records in their input order.

For example, if you sort only by department:

stable_sort(records, key = department)

then employees within the same department remain in their original order.

With an unstable sort, that internal order may change.

Multi-Pass Sorting

Stable sorting allows multi-pass record sorting.

To sort by department first and salary second, apply the less important key first:

stable_sort(records, key = salary)
stable_sort(records, key = department)

The final order is by department. Within each department, salary order remains because the second pass is stable.

For descending salary, use:

stable_sort(records, key = salary, descending = true)
stable_sort(records, key = department)

Correctness

The key function maps each record to an ordering value. Sorting by the key is correct when the key order matches the desired record order.

For two records a and b, the output order is determined by:

key(a) <= key(b)

If the key is lexicographic, earlier key components dominate later ones. Later components only matter when earlier components are equal.

The permutation condition holds because the algorithm moves records, not only keys. Every output record must be one of the input records.

Preserving Record Identity

Do not sort keys separately from records unless you maintain a link between them.

Incorrect pattern:

keys = [key(r) for r in records]
sort(keys)

This loses the association between keys and records.

Correct pattern:

pairs = [(key(r), r) for r in records]
sort(pairs)
records = [r for (_, r) in pairs]

This is the decorate-sort-undecorate pattern.

Handling Missing Fields

Real records often contain missing values. Define a policy before sorting.

Common policies:

missing values first
missing values last
missing values treated as zero
missing values rejected as invalid

The policy must be consistent. Inconsistent handling can break comparator transitivity.

Example:

key(record):
  if record.salary is missing:
    return (record.department, 1, 0)
  else:
    return (record.department, 0, -record.salary)

Here the second key component places present salaries before missing salaries.

Complexity

If sorting uses comparison sort, the number of comparisons is usually:

O(n log n)

If key extraction costs c, extracting the key inside every comparison can be expensive.

A comparator may compute keys repeatedly:

O(c n log n)

Decorating records computes each key once:

O(c n)

then sorts decorated pairs:

O(n log n)

This is often faster when key extraction is nontrivial.

Implementation Notes

Use key extraction when the language supports it. It is concise, testable, and usually safer than hand-written comparator code.

Use comparators when the order cannot be expressed cleanly as a tuple key, or when comparison must short-circuit expensive fields.

Keep the original index if stable behavior is required but the sort implementation is unstable:

key(record, index):
  return (primary_key(record), index)

This forces equal keys to preserve input order.

Common Bugs

A common bug is sorting only the key array and forgetting to move records with their keys.

Another bug is reversing the whole tuple when only one field should be descending. For mixed ascending and descending fields, transform only the descending component.

A third bug is leaving missing values undefined. Sorting must know how to compare every pair of records.

A fourth bug is using an unstable sort for multi-pass sorting. The second pass may destroy the order created by the first pass.

Takeaway

Sorting records is mostly about defining the right key. Once the key is correct, ordinary sorting machinery applies. Stability, missing-value policy, and key extraction cost determine the practical implementation.