2.1.4 Sorting Algorithms

In this lesson, you will learn how standard sorting algorithms are used to arrange values into order. You will explore bubble sort, merge sort, and insertion sort, apply each algorithm to data sets, compare how they work, and learn to recognise their key features in code or pseudocode.

Standard Sorting Algorithms

A sorting algorithm is a sequence of instructions used to arrange data into a particular order, such as numerical order or alphabetical order.

The three sorting algorithms you need to know are bubble sort, insertion sort, and merge sort. Although all three can produce the same sorted list, they achieve this in very different ways.

Bubble Sort

A bubble sort repeatedly compares adjacent values and swaps them when they are in the wrong order.

A complete journey through the list is called a pass. During a pass, adjacent pairs are considered from left to right. For an ascending sort, if the value on the left is larger than the value on the right, the two values are swapped. This causes larger values to gradually move towards the end of the list.

The process repeats until an entire pass is completed without any swaps. Only then can the algorithm be certain that the list is sorted.

Suppose we want to sort the following list into ascending order:

[15, 2, 8, 1, 12, 5]

During the first pass, bubble sort begins by comparing the first pair of adjacent values, 15 and 2:

[\underline{15}, \underline{2}, 8, 1, 12, 5]

Because $15 > 2$ , the values are in the wrong order for an ascending sort, so they are swapped:

[2, 15, 8, 1, 12, 5]

Next, 15 and 8 are compared:

[2, \underline{15}, \underline{8}, 1, 12, 5]

Since $15 > 8$ , they are swapped:

[2, 8, 15, 1, 12, 5]

Next, compare 15 and 1. Since $15 > 1$ , swap them:

[2, 8, 1, 15, 12, 5]

Then compare 15 and 12. Since $15 > 12$ , swap them:

[2, 8, 1, 12, 15, 5]

Finally, compare 15 and 5. Since $15 > 5$ , swap them:

[2, 8, 1, 12, 5, 15]

The first pass is now complete. Although 15 is now in its final position, the rest of the list may still be unsorted, so another pass is required.

After the second pass, the list becomes:

[2, 1, 8, 5, 12, 15]

After the third pass, it becomes:

[1, 2, 5, 8, 12, 15]

The list now looks sorted, but bubble sort does not stop simply because the values appear to be in order. It must complete another pass. If this final pass produces no swaps, the algorithm can confirm that the list is sorted.

The same repeated comparison-and-swap process can be seen in program code. In the implementation in Code 1 below, the for loop moves through adjacent pairs in the list, while the while loop repeats complete passes until no swaps are made.

Codepython

numbers = [15, 2, 8, 1, 12, 5]

sorted_list = False

while not sorted_list:
    sorted_list = True

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

print(numbers)

Code 1. Python code implementing bubble sort by repeatedly comparing adjacent values and swapping them until a complete pass occurs with no swaps.

The outer $while$ loop controls the repeated passes through the list, while the inner $for$ loop compares each adjacent pair during a single pass.

The expression $numbers[i] > numbers[i + 1]$ compares two adjacent values. If they are in the wrong order, the following line swaps them. Whenever a swap occurs, $sorted_list$ is set back to $False$ , which means another pass will be required.

These are the key features that make bubble sort recognisable in code or pseudocode: adjacent values are repeatedly compared and swapped, and passes continue until the algorithm completes one without making a swap.

Merge Sort

A merge sort uses a divide and merge approach. It first divides a list into progressively smaller sub-lists and then merges those sub-lists back together in sorted order.

There are two stages:

Divide: Repeatedly divide the list until every sub-list contains just one value.
Merge: Combine the sub-lists back together in sorted order until one complete sorted list remains.

Consider the following list:

[10, 6, 8, 4, 2, 9]

The algorithm begins with the divide stage, where the list is divided into two smaller sub-lists:

[10, 6, 8] [4, 2, 9]

Neither sub-list contains only one value, so they must be divided again:

[10] [6, 8] [4] [2, 9]

The remaining two-value lists are divided one final time:

[10] [6] [8] [4] [2] [9]

Every sub-list now contains one value. A single value is already considered to be in sorted order, so the divide stage is complete.

Once every sub-list contains a single value, the merge stage begins. The algorithm now combines neighbouring sub-lists that were created from the same parent list back together, working from the smallest sub-lists upwards. Each pair is merged into a new sorted sub-list before moving on to the next pair.

The first pair to be merged is the neighbouring sub-lists $[6]$ and $[8]$ , because together they originally formed the sub-list $[6, 8]$ during the divide stage. Since $6 < 8$ , they are merged as:

[6, 8]

Similarly, the neighbouring sub-lists $[2]$ and $[9]$ are merged, because together they originally formed $[2, 9]$ :

[2, 9]

This gives:

[10] [6, 8] [4] [2, 9]

The algorithm now moves up to the next level. The single-value sub-list $[10]$ is merged with the sorted sub-list $[6, 8]$ , because together they originally formed $[10, 6, 8]$ .

Compare the first remaining value from each list: 10 and 6. Since 6 is smaller, 6 is placed first.

Next compare 10 with 8. Since 8 is smaller, 8 is placed next.

Only 10 remains, so it is added at the end:

[6, 8, 10]

At the same level, $[4]$ is merged with $[2, 9]$ , because together they originally formed $[4, 2, 9]$ .

Compare 4 and 2. Since 2 is smaller, 2 is placed first.

Then compare 4 and 9. Since 4 is smaller, 4 is placed next.

Only 9 remains, so it is added last:

[2, 4, 9]

There are now two sorted sub-lists:

[6, 8, 10] [2, 4, 9]

These are merged in exactly the same way.

Compare 6 and 2. Since 2 is smaller, place 2 first:

[2]

Compare 6 and 4. Since 4 is smaller, place 4 next:

[2, 4]

Compare 6 and 9. Since 6 is smaller, place 6 next:

[2, 4, 6]

Compare 8 and 9. Since 8 is smaller, place 8 next:

[2, 4, 6, 8]

Compare 10 and 9. Since 9 is smaller, place 9 next:

[2, 4, 6, 8, 9]

Only 10 remains, so it is added last. The final sorted list is therefore:

[2, 4, 6, 8, 9, 10]

The defining pattern of merge sort is therefore its divide-and-merge structure: the original list is repeatedly divided until each sub-list contains one item, and the sub-lists are then progressively merged back together in sorted order.

Insertion Sort

An insertion sort treats the list as having two sections: a sorted section and an unsorted section.

Initially, the sorted section contains only the first item. The algorithm then takes each item from the unsorted section in turn and inserts it into the correct position in the sorted section.

Consider the following list:

[17, 3, 11, 6, 21, 9]

Initially, only the first value is considered sorted:

Sorted [17] Unsorted [3, 11, 6, 21, 9]

The next value is 3. It is compared with the values in the sorted section. Since $3 < 17$ , it must be inserted before 17:

Sorted [3, 17] Unsorted [11, 6, 21, 9]

The next value is 11. It is larger than 3 but smaller than 17, so it is inserted between them:

Sorted [3, 11, 17] Unsorted [6, 21, 9]

Next, 6 is taken from the unsorted section. It is smaller than 17 and 11, so these values move to the right. It is larger than 3, so it is inserted after 3:

Sorted [3, 6, 11, 17] Unsorted [21, 9]

The next value is 21. Since 21 is larger than every value in the sorted section, no values need to be moved, so it remains at the end:

Sorted [3, 6, 11, 17, 21] Unsorted [9]

Finally, 9 is taken from the unsorted section. It is smaller than 21, 17, and 11, so these values move to the right. It is larger than 6, so 9 is inserted between 6 and 11:

Sorted [3, 6, 9, 11, 17, 21]

There are now no values remaining in the unsorted section, so the entire list is sorted.

Unlike bubble sort, insertion sort does not need a final pass to check whether the list is sorted. Once every item has been inserted into the sorted section, the algorithm is complete.

The same process of building a sorted section can be seen in the Python implementation in Code 2 below. The loop starts at the second item because the first item is initially treated as sorted. Each new value is stored, compared with values to its left, and inserted into the correct position in the sorted section.

Codepython

numbers = [17, 3, 11, 6, 21, 9]

for i in range(1, len(numbers)):
    current_value = numbers[i]
    j = i - 1

    while j >= 0 and numbers[j] > current_value:
        numbers[j + 1] = numbers[j]
        j -= 1

    numbers[j + 1] = current_value

print(numbers)

Code 2. Python code implementing insertion sort by taking each new value and inserting it into the correct position within the sorted section of the list.

The variable $current_value$ stores the item that is being inserted. The $while$ loop then works backwards through the sorted section. Any value larger than $current_value$ is shifted one position to the right until the correct insertion point is reached.

This gives insertion sort its distinctive pattern in code or pseudocode: it usually starts from the second item, works backwards through an already sorted section, shifts larger values to the right, and inserts the current value into the gap that remains.

Comparing Sorting Algorithms

Bubble sort, merge sort, and insertion sort all produce a sorted list, but they use very different methods to achieve this. As a result, each algorithm has different strengths and limitations depending on the size and existing order of the data.

Table 1. Comparison of bubble sort, merge sort, and insertion sort.

Characteristic	Bubble Sort	Merge Sort	Insertion Sort
Method	Compare and swap adjacent values.	Divide into smaller lists, then merge them in order.	Build a sorted section one value at a time.
Completion Condition	A complete pass occurs with no swaps.	All sub-lists have been merged into one sorted list.	Every value has been inserted into the sorted section.
Advantage	Simple to understand and implement.	Generally efficient for large lists.	Effective for small or nearly sorted lists.
Limitation	Can require many comparisons and passes.	Requires additional memory for sub-lists.	Can require many movements for badly ordered data.

There is no single sorting algorithm that is best in every situation. Bubble sort is simple but can be slow for large lists, insertion sort can work well with small or nearly sorted lists, and merge sort is generally more efficient for large data sets but requires additional memory to create and merge sub-lists.

GCSE

University Taster