Recognising Sorting Algorithms in Code

You can often recognise a sorting algorithm from the shape of its code, even when the variable names differ. Look at how items are compared and moved rather than memorising exact lines.

Code clue	Algorithm	What the code is doing
Neighbouring items are compared and swapped using a temporary variable, and a swapped flag repeats the passes. An outer loop repeats the passes while the flag shows a swap happened, and an inner loop compares neighbouring pairs; using `len()` minus one stops it before the final position.	Bubble sort	Each pass compares adjacent pairs and swaps only those in the wrong order. The flag records whether any swap happened, so the sort can stop after a pass with no swaps.
The list is split into left and right parts, then sorted lists are merged by comparing their front items into a result list.	Merge sort	The ordered merging is what sorts the data. The lists are not merged unsorted and sorted afterwards.
An item is taken from the next unsorted position, larger items shift right in an inner while loop, then the item is placed into the gap.	Insertion sort	The outer loop starts at the second item because the first item is already a sorted list of one item. The inner while loop is condition-controlled: the number of shifts is not known in advance.

In the bubble sort program, the temporary variable keeps a value safe before its position is overwritten. It stores a value, not an index. The swapped flag starts as True: each pass sets it to False, and any swap sets it back to True, so the while loop stops as soon as a whole pass makes no swaps.

heights = [152, 138, 171, 129]
swapped = True
while swapped:
    swapped = False
    for k in range(len(heights) - 1):
        if heights[k] > heights[k + 1]:
            hold = heights[k]
            heights[k] = heights[k + 1]
            heights[k + 1] = hold
            swapped = True
print(heights)

Output:

[129, 138, 152, 171]

In the insertion sort program, the outer loop starts at the second item and the inner while loop shifts larger items right until there is a gap for the current item.

queue = [23, 9, 17, 4, 11]
for i in range(1, len(queue)):
    held = queue[i]
    gap = i - 1
    while gap >= 0 and queue[gap] > held:
        queue[gap + 1] = queue[gap]
        gap = gap - 1
    queue[gap + 1] = held
print(queue)

Output:

[4, 9, 11, 17, 23]

You do not need to memorise these programs. Match the clues instead: neighbouring compare-and-swap with a flag, splitting and ordered merging, or shifting right before inserting.

Practise this