Sorting in real code: keys, comparators, counting sort

sorted() versus list.sort()

sorted(x) works on any iterable and returns a NEW list; the original is untouched. lst.sort() sorts the list in place and returns None, so lst = lst.sort() leaves you holding None. Both take the same two optional arguments: key and reverse. Both are O(n log n) in the worst case.

Key functions

A key function turns each item into the value to compare. It is called once per item, then the sort compares the keys. key=len sorts strings by length; key=str.lower ignores case; key=lambda s: s[1] sorts tuples by their second field. reverse=True sorts from largest to smallest and still keeps equal items in their original order.

words = ["kiwi", "Banana", "apple", "fig"]
print(sorted(words))                  # Output: ['Banana', 'apple', 'fig', 'kiwi']
print(sorted(words, key=str.lower))   # Output: ['apple', 'Banana', 'fig', 'kiwi']
print(sorted(words, key=len))         # Output: ['fig', 'kiwi', 'apple', 'Banana']

Sorting by several fields

Return a tuple from the key: Python compares tuples field by field, left to right. For "marks high to low, then name A to Z", negate the number: key=lambda s: (-s["marks"], s["name"]). Negation works only for numbers. For descending strings, use stability instead: sort by the second field first, then by the first field; the second sort keeps the order of the first among ties.

students = [("Ravi", 75), ("Asha", 82), ("Kiran", 75), ("Meena", 82)]
print(sorted(students, key=lambda s: (-s[1], s[0])))
# Output: [('Asha', 82), ('Meena', 82), ('Kiran', 75), ('Ravi', 75)]

# Same result with two stable sorts: secondary key first, then primary
by_name = sorted(students, key=lambda s: s[0])
print(sorted(by_name, key=lambda s: s[1], reverse=True))
# Output: [('Asha', 82), ('Meena', 82), ('Kiran', 75), ('Ravi', 75)]

Timsort: what Python uses

Python's sort is Timsort, a hybrid of merge sort and insertion sort designed by Tim Peters for Python. It finds runs that are already sorted, extends short runs with insertion sort, and merges runs. So it is O(n log n) in the worst case, O(n) when the input is already sorted, stable, and may use up to O(n) extra memory. V8, the engine in Chrome and Node.js, also uses Timsort for Array.prototype.sort.

Custom comparisons: cmp_to_key

Sometimes the order is defined by comparing two items, not by a key per item. Classic example: arrange numbers to form the largest number. 9 should come before 34, and 3 before 30, because "330" > "303". The rule is: a goes first if a + b > b + a as strings. A comparator returns a negative number if a should come first, positive if b should, and 0 for a tie. functools.cmp_to_key turns it into a key.

from functools import cmp_to_key

def compare(a, b):
    if a + b > b + a:
        return -1          # a first
    if a + b < b + a:
        return 1           # b first
    return 0

nums = [3, 30, 34, 5, 9]
parts = sorted(map(str, nums), key=cmp_to_key(compare))
print("".join(parts))   # Output: 9534330

Counting sort: O(n + k) for small ranges

When the values are integers in a small range 0..k, like exam marks 0 to 100 or ages, you do not need comparisons at all. Count how many times each value appears in an array of size k + 1, then write each value out count times. That is O(n + k) time and O(k) extra space, faster than O(n log n) when k is not much bigger than n. It is useless when the range is huge (phone numbers), because the count array would be enormous.

marks = [72, 95, 72, 40, 100, 95]
count = [0] * 101
for m in marks:
    count[m] += 1
result = [v for v in range(101) for _ in range(count[v])]
print(result)   # Output: [40, 72, 72, 95, 95, 100]

JavaScript sort pitfalls

Without a comparator, Array.prototype.sort converts items to strings and compares them as text, so [10, 9, 1].sort() gives [1, 10, 9], because "10" comes before "9" as text. Always pass a comparator for numbers: (a, b) => a - b for ascending. A comparator must return a number (negative, zero or positive); returning a boolean such as a > b gives wrong results in some engines. sort also changes the array in place; copy first with [...arr].sort(…) or use arr.toSorted(…) (ES2023). Since ES2019, sort is required to be stable.

console.log([10, 9, 1].sort());                 // Output: [ 1, 10, 9 ]
console.log([10, 9, 1].sort((a, b) => a - b));  // Output: [ 1, 9, 10 ]
const people = [{ n: "Ira", age: 30 }, { n: "Om", age: 25 }];
console.log([...people].sort((a, b) => a.age - b.age).map((p) => p.n));   // Output: [ 'Om', 'Ira' ]

Common mistakes

• Writing lst = lst.sort(), which sets lst to None. Fix: use lst.sort() alone, or new = sorted(lst).
• Negating a string in a tuple key (-name raises TypeError). Fix: two stable sorts, or cmp_to_key.
• Calling .sort() with no comparator on numbers in JavaScript. Fix: (a, b) => a - b.
• Using counting sort when the range is huge or the values are not integers. Fix: use it only for small integer ranges.
• Forgetting the "all zeros" case in largest number: [0, 0] should give "0", not "00". Fix: if the first part is "0", return "0".