PYTHON / DATA STRUCTURES AND ALGORITHMS
Sorting algorithms
Implement insertion sort and merge sort by hand, and use key= plus stability rules to control how Python's built-in sort orders records.
What you will learn
- Write insertion sort by shifting values into a growing sorted prefix
- Write merge sort and see why the merge step is where ordering happens
- Use key= so each element is measured once instead of comparing manually
- Order by several fields with stable sorts, least significant field first
Understanding Sorting algorithms
Insertion sort keeps a sorted prefix at the front of the list and inserts one more element into it on every pass. The insertion is done by shifting larger values one slot to the right until a gap opens in the right place, which is why the cost is dominated by moves rather than by comparisons. On a list that is already almost in order each element only shifts a slot or two, so the algorithm is genuinely fast there; on a reversed list every element shifts past the whole prefix and the work grows with the square of the length.
Merge sort attacks the same problem from the other side: split the list in half until pieces have one element, then merge two ordered pieces into one ordered piece by repeatedly taking the smaller front element. Splitting does no ordering work at all; every ordering decision happens in the merge, and each merge level touches every element once, which is where the log-many-levels times n-per-level behaviour comes from. The price is a second buffer, since you cannot merge two halves into their own space without extra room. If you break the tie in the merge by taking from the left half, equal elements keep their original relative order, which is what stability means.
Python's list.sort and sorted use Timsort, a merge sort that first looks for runs of already-ordered elements and uses insertion sort on short pieces, so real-world partly ordered data costs far less than random data. Both accept key=, which calls your function once per element and sorts by the returned values, so an expensive computation is not repeated inside every comparison. Both are stable, and reverse=True keeps that stability, meaning tied elements are not flipped. You write insertion sort and merge sort to understand ordering, not to ship them: the built-in runs its comparisons in C.
def insertion_sort(values):
a = list(values)
for i in range(1, len(a)):
current = a[i]
j = i - 1
while j >= 0 and a[j] > current:
a[j + 1] = a[j]
j -= 1
a[j + 1] = current
print(f"after placing {current}: {a}")
return a
data = [5, 2, 9, 1, 5, 6]
result = insertion_sort(data)
print("result:", result)
print("matches sorted():", result == sorted(data))
print("original untouched:", data)A sort is defined by how it uses comparisons to move elements, and the choice of algorithm decides both the number of moves and whether equal elements keep their original order.
Worked examples
Merge sort and the merge step
Shows that all ordering work in merge sort happens inside a single linear merge of two ordered lists.
def merge(left, right):
out = []
i = j = 0
while i < len(left) and j < len(right):
if right[j] < left[i]:
out.append(right[j])
j += 1
else:
out.append(left[i])
i += 1
out.extend(left[i:])
out.extend(right[j:])
return out
def merge_sort(a):
if len(a) <= 1:
return list(a)
mid = len(a) // 2
return merge(merge_sort(a[:mid]), merge_sort(a[mid:]))
print(merge_sort([38, 27, 43, 3, 9, 82, 10]))
print(merge([1, 4, 6], [2, 3, 7]))Example explained
Line 1len(a) <= 1 is the base case: a one-element list is already ordered, so no comparison is needed.
Line 2The while loop advances only one index per iteration, so a merge of n total elements costs n appends.
Line 3The test right[j] < left[i] takes from the left half on ties, which is what makes this merge stable.
Line 4The two extend calls flush whatever remains of the half that was not exhausted.
Ordering by two fields with stable sorts
Demonstrates that stability lets you build a multi-field order by sorting the least significant field first.
records = [("ana", 3), ("bo", 1), ("cy", 3), ("dee", 1)]
print(sorted(records, key=lambda r: r[1]))
people = [("ana", 3), ("bo", 1), ("cy", 3), ("dee", 1)]
people.sort(key=lambda r: r[0], reverse=True)
people.sort(key=lambda r: r[1])
print(people)Example explained
Line 1The first sort only looks at r[1], so 'bo' stays before 'dee' because that was their input order.
Line 2The name sort with reverse=True runs first because name is the less significant field.
Line 3The second sort groups by score and, being stable, preserves the reverse-name order inside each score group.
Line 4sorted returns a new list while people.sort rewrites people in place and returns None.
Comparisons must be defined
Shows that a comparison sort fails on values that cannot be compared, and how key= supplies the ordering instead.
words = ["pear", "Fig", "apple", "banana"]
print(sorted(words))
print(sorted(words, key=str.lower))
try:
sorted([3, "1", 2])
except TypeError:
print("cannot compare str with int")Example explained
Line 1Plain string comparison uses code points, so 'Fig' sorts before every lowercase word.
Line 2key=str.lower is called once per word and the sort compares the lowercased copies, leaving the originals intact.
Line 3A mixed int/str list raises TypeError on the very first comparison, so nothing is sorted at all.
Line 4Passing key=str.lower rather than str.lower(words) matters: the sort needs the function, not a result.
Important notes
sorted accepts any iterable and returns a new list; list.sort exists only on lists and returns None.
Stability is a property of the algorithm, not of sorting in general: quicksort and heapsort can reorder equal elements, so do not substitute them where ties carry meaning.
Common mistakes
Writing values = mylist.sort(): sort mutates in place and returns None, so values becomes None and the next line raises TypeError.
Sorting by the primary field first and the secondary field last, which regroups the data by the secondary field and destroys the intended order.
Forgetting the j >= 0 guard in the insertion loop, so a[j] with j == -1 reads the last element and the smallest value is silently placed wrong.
Try it yourself
Change, predict, then run
Write selection sort that scans for the smallest remaining element, swaps it into place, and counts swaps; run it on [4, 3, 2, 10, 12, 1, 5, 6] and confirm the result equals sorted() while the swap count is at most len(list) - 1.
Open the Python workspaceCheck your understanding
You have a list of (name, score) pairs and want it ordered by score ascending, with names alphabetical among equal scores, using two calls to list.sort. Which sequence works?
- Sort by name, then sort by score
- Sort by score, then sort by name
- Sort by score with reverse=True, then sort by name
- Either order works, because Python's sort is stable
Show answer
Stability preserves the existing order only for elements the current key considers equal, so the last sort must use the most significant field. Sorting by name first leaves names in order inside each score group after the score sort. Sorting by score first is tempting but the final name sort compares every pair by name and scatters the score grouping completely.