Comparing Bubble Sort and Merge Sort

Bubble sort and merge sort can both put the same list into order, but they do different amounts of work and they use memory in different ways. Merge sort is usually the faster of the two, especially once a list gets long.

Dividing the work

Merge sort is divide-and-conquer: it keeps splitting the list into smaller parts down to single items, then merges them back. Each merge only compares the next item of two sorted lists, so the total number of comparisons stays low. Bubble sort is not divide-and-conquer: it repeatedly compares neighbouring pairs across the list, so its comparisons pile up as the list grows. For a list of 10 items, bubble sort can need up to 45 comparisons, while merge sort needs at most 25. Double the list to 20 items and bubble sort can need 190 comparisons against about 69 for merge sort, so the gap grows quickly.

Memory

Merge sort is out-of-place: splitting and merging build extra sub-lists, so it has a higher memory overhead. Bubble sort is in-situ: it swaps items inside the original list, so its storage stays constant however long the list is. Being faster does not make merge sort cheaper on memory.

Judging efficiency and fitness for purpose

You can evaluate a sorting algorithm on three measures: the number of comparisons, the number of passes or loop iterations, and the amount of memory used. More comparisons mean more work, so the program takes longer to run; fewer comparisons mean it finishes sooner.

So the best choice depends on the situation: speed first means merge sort, memory first means bubble sort. The program below counts its own passes and comparisons as it uses a bubble sort on four lap times in seconds.

lap_times = [58, 43, 61, 37]
comparisons = 0
passes = 0
for pass_number in range(1, len(lap_times)):
    passes = passes + 1
    for i in range(len(lap_times) - pass_number):
        comparisons = comparisons + 1
        if lap_times[i] > lap_times[i + 1]:
            temp = lap_times[i]
            lap_times[i] = lap_times[i + 1]
            lap_times[i + 1] = temp
print("passes: " + str(passes))
print("comparisons: " + str(comparisons))
print(lap_times)

Output:

passes: 3
comparisons: 6
[37, 43, 58, 61]