Custom Sorting: Beginner

Python ships 2 sorting entry points over the same Timsort engine, and they differ in 1 contract: what happens to the data passed in. sorted() accepts any iterable, builds a new list, sorts that new list and returns it. list.sort() exists only on lists, rearranges the list it is called on, and returns None. Interviewers probe the difference because it decides whether a function has a side effect on its caller.

The most frequent bug here is assigning the result of .sort(). Read the program below and decide what each of its 3 print lines produces before reading on.

The first print shows None, because .sort() returns nothing. The second shows [7, 19, 42]: the sort happened, on the list under its old name. The third raises TypeError: 'NoneType' object is not subscriptable. In a pipeline that error tends to surface far from its cause, inside whatever function later received ranked as an argument, which makes it slow to trace.

Both functions take key= and reverse=. The key function maps each element to the value that gets compared. Python calls it exactly once per element, stores the results, and then compares only those stored keys, however many comparisons the sort needs. A key that costs 1 millisecond therefore adds about 17 minutes on 1,000,000 rows, and that figure stays fixed whether the input is random or nearly sorted. The run below logs every key call so you can count them.

sorted() logs 3 key calls for 3 rows, returns the reordered list, and leaves tracks exactly as it was. .sort() logs 3 more calls, returns None, and reorders tracks itself. The final count of 6 confirms one call per element per sort, never one per comparison.

Pipeline rows usually arrive as dicts or tuples, and the key is usually one field. operator.itemgetter('streams') builds a callable that performs the same lookup as lambda r: r['streams'], but the lookup runs in C instead of executing a Python function body for every row. Given several field names, itemgetter('artist', 'streams') returns a tuple per row, which is the building block for multi-field ordering. For objects with attributes, operator.attrgetter('streams') plays the same role.

The first line prints ['Drift', 'Halo', 'Ember'], highest count first. The second prints ('Nova', 30): a tuple built from the first row, in the order the field names were given. plays itself still starts with Halo, because sorted() never touched it.

Iterating a dict yields its keys, so sorted(counts) returns the key names alphabetically and drops the counts. To rank by value, sort the (key, value) pairs from .items() with itemgetter(1). Dicts have no .sort() method, and neither do tuples or generators, so for them sorted() is the only choice.

This prints ['Arlo', 'Kite', 'Nova'], then [('Kite', 40), ('Arlo', 25), ('Nova', 12)], and the last line raises AttributeError: 'dict' object has no attribute 'sort'. The ranked result is a list of pairs; wrap it in dict() if a dict in that order is what the caller wants.

Sorting compares keys with <, and Python 3 refuses to compare unrelated types. A column holding a stray string or a None stops the whole sort with an error, so a bad value never produces a quietly half-sorted result. sorted([3, None, 1]) raises TypeError: '<' not supported between instances of 'NoneType' and 'int'. Missing values are routine in real feeds, so plan the key for them; the next section shows a key that places them first or last on purpose.

The last row matters later in this section: booleans compare as False < True, so a boolean in the first slot splits rows into 2 groups before any other field is consulted.

reverse=True flips the entire key, so it cannot make one slot descend while another ascends. For a numeric field, negate it inside the key: -r['streams'] turns the largest count into the smallest key value. The key (r['artist'], -r['streams'], r['track']) reads as artist from A to Z, most streamed first within each artist, and track name from A to Z when 2 tracks of one artist tie on streams.

Negation needs a number. -'Kite' raises TypeError: bad operand type for unary -: 'str', and a datetime.date refuses unary minus in the same way. Three workarounds cover most interview cases:

Real columns contain None, and a single one stops a plain sort. Put a boolean in front of the field: s is None is False for rows with a value and True for rows without, and since False < True, missing values land last. For the numeric slot, -(s or 0) turns a missing value into 0, so None never enters the key at all, and the leading boolean keeps those placeholder zeros apart from real counts. The shorter key (s is None, s) would also work: 2 None slots compare equal with ==, so the comparison moves on to the next slot. A None meets < only when it sits in the first slot that differs, and the boolean in front rules that out.

This prints ['Drift', 'Halo', 'Aura', 'Glow']. Drift and Halo carry False and order by descending streams; Aura and Glow carry True, tie on the 0 placeholder, and fall back to track name. To put missing values first instead, lead with s is not None. Writing the key as a named function, as here, also gives a reviewer one place to read the full ordering rule.

A sort is stable when rows with equal keys come out in the same relative order they went in. The Python documentation guarantees stability for both sorted() and list.sort(), and states that reverse=True keeps the guarantee. Interviewers ask about it because 2 everyday techniques depend on it: chaining sorts, and deduplicating by keeping one record per key.

The first line prints [('Nova', 30), ('Arlo', 30), ('Kite', 50), ('Mira', 50)] and the second prints [('Kite', 50), ('Mira', 50), ('Nova', 30), ('Arlo', 30)]. In both, Nova stays ahead of Arlo and Kite stays ahead of Mira, matching their positions in rows. reverse=True inverts the comparison while holding equal rows in their original sequence; reversing the finished ascending list would have put Mira before Kite.

A classic pipeline task: a change feed delivers several versions of each customer row, and the target table needs only the newest version per customer_id. Sort the events by updated_at ascending, then write them into a dict keyed by customer_id. Later writes overwrite earlier ones, so each key ends holding its newest version. Stability settles the hard case. When 2 versions share an updated_at, they stay in arrival order, so the one that arrived last wins, a rule you can state and defend.

The program prints 7 gold and 9 plus. ISO 8601 strings in a single fixed format and timezone order the same way as the instants they encode, so no parsing is needed. Customer 7 has 2 versions at 2024-03-02T10:00; the sort keeps silver ahead of gold, and the dict keeps gold. With an unstable sort, which of silver and gold survives would depend on the algorithm's internals rather than on arrival order, so the result could change when the feed's order or the library changes.

To keep the earliest version per key instead, sort the same way and skip any key already present: if e['customer_id'] not in first: first[e['customer_id']] = e. Stability again decides ties, this time in favour of the version that arrived first.

Every solution so far assumed the rows already sit in a Python list. In a data engineering interview, the strongest first move after hearing a sorting prompt is a question: how many rows, and how big is each one? The answer decides whether sorted() is the whole solution, whether the sort belongs in the query engine, or whether the data has to be sorted in pieces.

Every Python object carries a header, so a row costs several times its raw bytes. Take one play record stored as a tuple, ('user_123456', 4821, 3.75). As a CSV line, user_123456,4821,3.75 plus its newline, it is 22 bytes. On 64-bit CPython 3.9, sys.getsizeof reports these sizes for its parts:

On 64-bit CPython 3.9 this prints [64, 60, 28, 24] and then 184, the 8 being the list slot. The row costs about 8 times its CSV size. At 10,000,000 rows that comes to 1.84 GB before any sorting starts, and sorted() then adds a second list of references, another 80 MB. A tuple key adds a freshly built tuple per row for the duration of the sort, and Timsort's merge step borrows temporary space of up to half the list's references.

A working rule: sort in memory when the estimate, plus the copy and the keys, stays well under the RAM the process may use. Keep roughly half in reserve, because the interpreter and the rest of the program need memory too. Past that line, one sorted() call either fails with MemoryError or pushes the machine into swap, where every page fault waits on the disk and the job's runtime grows by orders of magnitude.

When the rows already sit in a table, the cheapest sort is often the one Python never runs. A query engine sorts across many workers and spills to disk on its own, and with a LIMIT it can keep only the top rows instead of ordering everything.

The merge step already exists in the standard library. heapq.merge takes any number of sorted iterables and yields one sorted stream, reading lazily and holding a single element from each input. It accepts the same key= and reverse= arguments as sorted().

This prints [1, 3, 5, 6, 9, 10, 12, 14, 20]. In a real external sort each run would be read row by row from storage, and the list call at the end would be replaced by writing each row out as it is produced.

Building the full external sort, with run files and a hand-written k-way heap merge, is the subject of a later lesson in this track.

Prompts that say 'top 10', 'the 5 slowest', 'the 3 most frequent' or 'the highest scorer' ask for K rows, and ordering the other rows is wasted work. Sorting all n rows to read the first K does O(n log n) work and holds every row. A min-heap of size K does O(n log K) work and holds K rows, and Python's heapq module packages it as 2 functions.

The first line prints ['Drift', 'Ember', 'Halo'] and the second prints ['Pulse', 'Halo']. Halo and Aster tie at 30 streams. The documentation defines nlargest(k, it, key=f) as equivalent to sorted(it, key=f, reverse=True)[:k], and nsmallest likewise without the reverse, so ties resolve as the stable sort would: Halo appears first in weekly, so Halo wins both times.

For n = 10,000,000 and K = 10, a comparison sort needs about n log2 n, roughly 233 million comparisons. The heap's worst case is about n log2 K, roughly 33 million, and it holds 10 rows instead of a second 10,000,000-entry list. The advantage shrinks as K grows: the documentation notes that for larger K, sorted() is more efficient, and that for K = 1, min() and max() are the better calls.

Prompt: the top 3 tracks by streams, ties broken by track name from A to Z. Calling nlargest with the key (streams, track) breaks ties from Z to A, because it maximizes the whole tuple, name included. Flip the problem: ask for the 3 smallest of (-streams, track). That is the negated tuple key from earlier in the lesson, handed to nsmallest.

The first line prints ['Drift', 'Ember', 'Halo'], because (30, 'Halo') is larger than (30, 'Aster'). The second prints ['Drift', 'Ember', 'Aster'], the answer the prompt asked for.

'Find the 3 most common error codes' is top K over counts. collections.Counter counts in one pass, and most_common(3) returns the 3 highest counts; given a number, CPython's implementation calls heapq.nlargest. The documentation guarantees that equal counts come back in the order their elements were first encountered.

This prints [('E42', 3), ('E17', 2), ('E99', 2)]. E17 and E99 tie at 2, and E17 comes first because it appeared first in codes.