What is a "key" in sorting?

AlgorithmsJunior~3 min read

Short answer

A sort key is a value (or a set of values) extracted from an element, which the algorithm uses to compare elements and determine their order. The key can be an object field, a computed expression, or a tuple of several fields.

Detailed breakdown

A sort key is a "projection" of an element onto a comparable value. Instead of comparing objects directly, we compare their keys. This simplifies the logic, speeds up sorting when computations are expensive, and makes behavior predictable.

Simple key: a single field or a single computed value (for example, user.age, a lowercased string, a date timestamp).
Composite key: a set of fields compared lexicographically (for example, (lastName, firstName, id)).
Computed key: the result of a function (for example, string length, a normalized form, a parsed date, natural order that accounts for numbers).
Rules for null/undefined/NaN: explicitly decide where to place them (first/last).

Key vs comparator

There are two approaches: provide a comparator (a function that returns -1/0/1) or provide a key-selector function. Python directly supports the key= parameter, while in JavaScript a comparator is usually written, but it is convenient to build a comparator from a key function. A comparator compares elements itself; a key function only returns the value that will be compared.

Key extraction (key selector) and composing keys

Single key: convert the object into a comparable value and sort by it.
Multiple keys: chain several comparators together; if the first key is equal, move on to the next one.
Decorate-Sort-Undecorate (Schwartzian transform): compute the expensive keys up front, sort by them, then "unwrap" the original elements.

Examples (JavaScript)

// Universal helpers for sorting by keys
function compareBy(keyFn, { order = 'asc', nulls = 'last', collator } = {}) {
  return (a, b) => {
    let ka = keyFn(a);
    let kb = keyFn(b);

    const isNilA = ka === null || ka === undefined;
    const isNilB = kb === null || kb === undefined;
    if (isNilA || isNilB) {
      if (isNilA && isNilB) return 0;
      return isNilA ? (nulls === 'first' ? -1 : 1) : (nulls === 'first' ? 1 : -1);
    }

    const isNaNA = typeof ka === 'number' && Number.isNaN(ka);
    const isNaNB = typeof kb === 'number' && Number.isNaN(kb);
    if (isNaNA || isNaNB) {
      if (isNaNA && isNaNB) return 0;
      return isNaNA ? 1 : -1; // Put NaN at the end
    }

    if (collator && typeof ka === 'string' && typeof kb === 'string') {
      const r = collator.compare(ka, kb);
      return order === 'asc' ? r : -r;
    }

    if (ka < kb) return order === 'asc' ? -1 : 1;
    if (ka > kb) return order === 'asc' ? 1 : -1;
    return 0;
  };
}

function compareByMany(...comparators) {
  return (a, b) => {
    for (const cmp of comparators) {
      const r = cmp(a, b);
      if (r !== 0) return r;
    }
    return 0;
  };
}

// Data
const users = [
  { id: 3, firstName: 'Oleh', lastName: 'green', age: 19 },
  { id: 1, firstName: 'Maria', lastName: 'Adams', age: 25 },
  { id: 2, firstName: 'MARIA', lastName: 'clark', age: 25 },
  { id: 4, firstName: 'Bob', lastName: null, age: undefined },
];

// 1) By a single key (numeric)
const byAgeAsc = users.slice().sort(compareBy(u => u.age, { order: 'asc', nulls: 'last' }));

// 2) By a string, case-insensitive and number-aware (natural sort)
const collator = new Intl.Collator('en', { sensitivity: 'base', numeric: true });
const byLastInsensitive = users.slice().sort(compareBy(u => u.lastName, { collator, nulls: 'last' }));

// 3) Composite key: lastName, then firstName, then id
const byLast = compareBy(u => u.lastName, { collator, nulls: 'last' });
const byFirst = compareBy(u => u.firstName, { collator, nulls: 'last' });
const byIdAsc = compareBy(u => u.id);
const byFullNameThenId = users.slice().sort(compareByMany(byLast, byFirst, byIdAsc));

// 4) Mixed direction: date descending, then name ascending
const orders = [
  { createdAt: '2024-05-01', name: 'zeta' },
  { createdAt: '2024-05-03', name: 'alpha' },
  { createdAt: '2024-05-03', name: 'bravo' },
];
const byDateDesc = compareBy(o => Date.parse(o.createdAt), { order: 'desc' });
const byNameAsc = compareBy(o => o.name, { collator: new Intl.Collator('en', { sensitivity: 'base' }) });
const ordersSorted = orders.slice().sort(compareByMany(byDateDesc, byNameAsc));

// 5) Decorate-Sort-Undecorate (Schwartzian transform) for an expensive key
const files = [
  { path: '/a/file9.txt' },
  { path: '/b/file10.txt' },
  { path: '/c/file2.txt' },
];
const natCollator = new Intl.Collator('en', { numeric: true, sensitivity: 'base' });
const sortedFiles = files
  .map(f => ({ f, k: f.path }))         // extract the key once
  .sort((x, y) => natCollator.compare(x.k, y.k))
  .map(({ f }) => f);

console.log({ byAgeAsc, byLastInsensitive, byFullNameThenId, ordersSorted, sortedFiles });

Example (Python)

users = [
    {"id": 3, "first": "Oleh", "last": "green", "age": 19},
    {"id": 1, "first": "Maria", "last": "Adams", "age": 25},
    {"id": 2, "first": "MARIA", "last": "clark", "age": 25},
    {"id": 4, "first": "Bob", "last": None, "age": None},
]

# By a single key (None goes last)
sorted_by_age = sorted(users, key=lambda u: (u["age"] is None, u["age"]))

# Composite key (lexicographic): last, first, id
sorted_by_name = sorted(
    users,
    key=lambda u: (
        (u["last"] or "").casefold(),
        (u["first"] or "").casefold(),
        u["id"],
    ),
)

# Mixed direction: descending by date, ascending by name
orders = [
    {"created_at": "2024-05-01", "name": "zeta"},
    {"created_at": "2024-05-03", "name": "alpha"},
    {"created_at": "2024-05-03", "name": "bravo"},
]
from datetime import datetime

def ts(s):
    return int(datetime.fromisoformat(s).timestamp())

sorted_orders = sorted(
    orders,
    key=lambda o: (-ts(o["created_at"]), o["name"].casefold())
)

print(sorted_by_age)
print(sorted_by_name)
print(sorted_orders)

Sort stability and the key

A stable sort preserves the relative order of elements with the same key. This matters for multi-step sorting: you can first sort by a secondary key, then by a primary key - the result will be the same as sorting by a composite key. In modern implementations, JavaScript's Array.prototype.sort is stable, and so is Python's sorted.

Pitfalls and recommendations

Numbers vs strings: '10' > '2' as strings. For "natural" sorting of strings containing numbers, use Intl.Collator(numeric: true) or number parsing.
Case and locale: use casefold()/toLowerCase() or Intl.Collator with the appropriate sensitivity settings.
null/undefined/NaN: define explicit rules for their position (first/last). Different engines behave differently by default.
Performance: if the key is expensive (date parsing, I/O, computation), use "decorate-sort-undecorate" (DSU) so the key is not computed repeatedly.
Memory vs speed: DSU adds allocations but reduces the number of key computations and comparisons.
Custom orders: for sorting by a predefined list (statuses), use a mapping to an index (map[status] → number) as the key.
Composite keys: do not concatenate fields into a single string without a reliable separator - use a sequence of comparators or tuples (in Python).

Terminology notes

A "sort key" is not necessarily a database "primary key." A primary key is unique and identifies a record, while a sort key is any expression used for ordering.
In a database, the role of the sort key is played by the expression in ORDER BY (a field, a function, several fields each with its own direction).

Short Answer

Interview ready

Premium

A concise answer to help you respond confidently on this topic during an interview.