Sorting algorithms

Bubble sort compares neighbouring items and swaps them if they are in the wrong order. After each pass, the largest unsorted item has moved to the end. The animation shows each comparison on 5, 1, 4, 2, 8, 3.

It takes four passes here; the last pass confirms there are no swaps. Bubble sort is easy to follow but does many comparisons on a long list.

FOR pass = 0 TO 4
    FOR i = 0 TO 4 - pass
        IF numbers[i] > numbers[i + 1] THEN
            temp = numbers[i]
            numbers[i] = numbers[i + 1]
            numbers[i + 1] = temp
        ENDIF
    NEXT i
NEXT pass

for pass_number in range(len(numbers) - 1):
    for i in range(len(numbers) - 1 - pass_number):
        if numbers[i] > numbers[i + 1]:
            numbers[i], numbers[i + 1] = numbers[i + 1], numbers[i]

Insertion sort grows a sorted section one item at a time. It takes the next item and inserts it into the correct place among the items already sorted. The animation compares the next value with earlier values and moves larger ones right.

On an almost-sorted list, insertion sort often needs fewer moves than bubble sort. Both are simple to follow, but merge sort is a better choice for a large list.

Starting with numbers = [5, 1, 4, 2, 8, 3], this Python loop sorts the list in place:

numbers = [5, 1, 4, 2, 8, 3]
for i in range(1, len(numbers)):
    key = numbers[i]
    j = i - 1
    while j >= 0 and numbers[j] > key:
        numbers[j + 1] = numbers[j]
        j -= 1
    numbers[j + 1] = key
print(numbers)

Merge sort splits a list into smaller parts until each part has one item, then merges parts back together in order. When merging, compare the next item in each part and take the smaller one.

The animation highlights values as the smaller parts are merged.

Merge sort needs extra space to hold parts while merging, but it handles large lists efficiently. Bubble and insertion sort are simpler to trace by hand; insertion sort can be effective when a list is already nearly in order.

def merge_sort(numbers):
    if len(numbers) <= 1:
        return numbers
    middle = len(numbers) // 2
    left = merge_sort(numbers[:middle])
    right = merge_sort(numbers[middle:])
    merged = []
    left_index = 0
    right_index = 0
    while left_index < len(left) and right_index < len(right):
        if left[left_index] <= right[right_index]:
            merged.append(left[left_index])
            left_index += 1
        else:
            merged.append(right[right_index])
            right_index += 1
    while left_index < len(left):
        merged.append(left[left_index])
        left_index += 1
    while right_index < len(right):
        merged.append(right[right_index])
        right_index += 1
    return merged

print(merge_sort([5, 1, 4, 2, 8, 3]))