Sorting algorithms: bubble, insertion and merge

Learn it by playing

Answer these questions to earn energy, then fish and explore. No account needed.

For educators: ready-to-use lesson slides, revision notes for Sorting algorithms: bubble, insertion and merge (KS3 Computing, Computer Science) — use them in your lesson, or run the topic as an interactive class activity your learners play as a live game.

Lesson notes

What is a Sorting Algorithm?

A sorting algorithm puts the elements of a list into a defined order, usually numerical or lexicographical (alphabetical).
The output must be in monotonic order – each element is no smaller (or no larger) than the previous one, depending on the required order.
The output must be a permutation of the input – it contains all the original elements, just rearranged.
Sorting is important because it makes other operations, like searching, faster and easier.
Sorting algorithms are often classified by their computational complexity – how the number of steps grows with the size of the list.

Bubble Sort

Bubble sort repeatedly steps through the list, compares adjacent items, and swaps them if they are in the wrong order.
Each pass through the list places the next largest (or smallest) element in its final position, like a bubble rising.
After each pass, the number of comparisons can be reduced by one because the last element is already sorted.
Bubble sort has O(n²) time complexity in the worst and average cases – it is inefficient for large lists.
It is a stable sort – equal elements keep their original relative order.
It is an in-place algorithm – it uses only a small constant amount of extra memory.

Insertion Sort

Insertion sort builds the sorted list one element at a time by taking each new element and inserting it into its correct position among the already-sorted elements.
It works like sorting playing cards in your hand – you pick up a card and place it where it belongs.
For each element, it compares with the elements before it and shifts them right until it finds the correct spot.
Insertion sort has O(n²) time complexity in the worst case, but O(n) in the best case when the list is already nearly sorted.
It is stable and in-place.
It is an online algorithm – it can sort a stream of data as it arrives.

Merge Sort

Merge sort is a divide-and-conquer algorithm: it splits the list into two halves, recursively sorts each half, then merges the two sorted halves back together.
The merge step repeatedly compares the front elements of the two halves and places the smaller one into the output.
Merge sort has O(n log n) time complexity in all cases – it is much faster than bubble or insertion sort for large lists.
It is stable – equal elements keep their relative order.
It is not in-place – it requires extra memory proportional to the size of the list (O(n)).
Merge sort is typically implemented recursively.

Comparing the Sorts

Bubble and insertion sort are simple but have O(n²) time – they are fine for small lists but slow for large ones.
Merge sort is more efficient with O(n log n) time, but it uses extra memory.
Insertion sort can be faster than merge sort for very small lists or nearly sorted lists because it has low overhead.
Bubble sort is rarely used in practice because it is usually slower than insertion sort for the same input.
The choice of algorithm depends on factors like list size, whether the list is nearly sorted, and memory constraints.

Working Through an Example

Consider sorting the list [5, 2, 4, 1, 3] in ascending order.
Bubble sort first pass: compare 5 and 2 → swap → [2,5,4,1,3]; compare 5 and 4 → swap → [2,4,5,1,3]; compare 5 and 1 → swap → [2,4,1,5,3]; compare 5 and 3 → swap → [2,4,1,3,5]. The 5 is now in place.
Insertion sort starts with [5] as sorted. Take 2 → insert before 5 → [2,5]. Take 4 → insert between 2 and 5 → [2,4,5]. Continue until all are placed.
Merge sort splits [5,2,4,1,3] into [5,2] and [4,1,3]. Recursively sort each half, then merge them: [2,5] and [1,3,4] merge to [1,2,3,4,5].
Counting comparisons and swaps helps compare the efficiency of each algorithm on the same data.

Key Terms

Comparison sort: a sort that only uses comparisons between elements to determine order.
Stable sort: preserves the relative order of equal elements.
In-place sort: uses only O(1) extra memory (or O(log n) in some definitions).
Time complexity: how the number of operations grows with input size, often expressed in Big O notation.
Divide-and-conquer: breaking a problem into smaller subproblems, solving them, and combining the results.

Slides

Step through every slide for this topic — plus flashcards and revision notes — with a free account.

Practice questions

Free preview — 8 of 60 questions. Sign up to see them all.

1.What is the primary purpose of a sorting algorithm?
Easy
- ATo arrange elements in a specific order
- BTo search for an element in a list
- CTo count the number of elements
- DTo remove duplicates from a list
2.Which of the following is NOT a common sorting algorithm?
Easy
- ABubble sort
- BInsertion sort
- CMerge sort
- DBinary sort
3.A stable sorting algorithm preserves the relative order of equal elements.
Easy
True or false?
4.Which sorting algorithm works by repeatedly comparing adjacent elements and swapping them if they are in the wrong order?
Medium
- ABubble sort
- BInsertion sort
- CMerge sort
- DSelection sort
5.Which sorting algorithm builds a sorted list one element at a time by inserting each new element into its correct position?
Medium
- ABubble sort
- BInsertion sort
- CMerge sort
- DQuick sort
6.Which of the following are true about merge sort? (Select all that apply)
Medium
- AIt uses a divide-and-conquer approach
- BIt is typically recursive
- CIt is an in-place sorting algorithm
- DIt has a worst-case time complexity of O(n log n)
7.Arrange the steps of a single pass of bubble sort on the list [5, 2, 4, 1] in the correct order.
Medium
- Compare 5 and 2, swap them to get [2, 5, 4, 1]
- Compare 5 and 4, swap them to get [2, 4, 5, 1]
- Compare 5 and 1, swap them to get [2, 4, 1, 5]
- The pass ends with the largest element 5 in its correct final position
8.Insertion sort is an 'online' algorithm because it can sort a stream of data as it arrives.
Medium
True or false?

Revision notes

## Sorting Algorithms: Bubble, Insertion, Merge ### What is Sorting? - Sorting puts elements of a list into order (numerical or lexicographical, ascending or descending). - A sorting algorithm must satisfy two conditions: 1. **Monotonic order**: each element is no smaller/larger than the previous, according to the required order. 2. **Permutation**: the output is a reordering of the input, retaining all original elements. - Efficient sorting is important for optimizing other algorithms like search and merge. ### Bubble Sort - **Method**: Repeatedly steps through the list, compares adjacent elements, and swaps them if they are in the wrong order. The pass through the list is repeated until no swaps are needed. - **Complexity**: Worst and average case O(n²) comparisons and swaps. Best case O(n) if already sorted. - **Stability**: Stable (equal elements keep their relative order). - **In-place**: Yes, uses O(1) extra memory. ### Insertion Sort - **Method**: Builds the final sorted array one item at a time. It takes each element and inserts it into its correct position among the previously sorted elements. - **Complexity**: Worst and average case O(n²) comparisons and swaps. Best case O(n) when nearly sorted. - **Stability**: Stable. - **In-place**: Yes. - **Online**: Can sort a stream of input as it arrives. ### Merge Sort - **Method**: A divide-and-conquer algorithm. It divides the list into halves, recursively sorts each half, then merges the sorted halves. - **Complexity**: Always O(n log n) comparisons in worst, average, and best cases. - **Stability**: Stable. - **Not in-place**: Typically uses O(n) extra memory for merging. ### Comparing Sorts - **Speed**: Merge sort is generally faster for large lists (O(n log n)) compared to bubble and insertion (O(n²)). - **Swaps**: Bubble sort often makes many swaps; insertion sort makes fewer; merge sort does not swap in-place but moves elements during merge. - **Use cases**: Insertion sort is good for small or nearly sorted lists; merge sort is good for large lists where speed matters. ### Key Concepts - **Comparison sort**: Examines data only by comparing two elements. - **Stability**: Maintains relative order of equal keys. - **In-place**: Needs only O(1) extra memory beyond the items being sorted. - **Adaptive**: Some algorithms (like insertion) run faster if input is partially sorted.

Sorting algorithm: An algorithm that puts elements of a list into an order, such as numerical or lexicographical order.
Monotonic order: The output is in monotonic order (each element is no smaller/larger than the previous element, according to the required order).
Permutation: The output is a permutation (a reordering, yet retaining all of the original elements) of the input.
Bubble sort: A simple sorting algorithm that repeatedly steps through the list, compares adjacent elements, and swaps them if they are in the wrong order. The pass is repeated until no swaps are needed.
Insertion sort: A sorting algorithm that builds the final sorted array one item at a time, inserting each element into its correct position among previously sorted elements.
Merge sort: A divide-and-conquer sorting algorithm that divides the list into halves, recursively sorts each half, then merges the sorted halves.
Stable sorting algorithm: A sorting algorithm that maintains the relative order of records with equal keys (i.e., values).
In-place sort: A sorting algorithm that needs only O(1) memory beyond the items being sorted; sometimes O(log n) additional memory is considered 'in-place'.
Comparison sort: A sorting algorithm that examines data only by comparing two elements with a comparison operator.
Computational complexity: The best, worst and average case behavior in terms of the size of the list. For typical serial sorting algorithms, good behavior is O(n log n), and bad behavior is O(n²).

Flashcards

What is a sorting algorithm?

An algorithm that puts elements of a list into an order, such as numerical or lexicographical order.

What are the two formal conditions the output of any sorting algorithm must satisfy?

The output must be in monotonic order (each element is no smaller/larger than the previous) and must be a permutation (reordering) of the input.

What is the typical best-case time complexity for comparison-based sorting algorithms?

O(n log n) for good serial sorting algorithms.

What is the typical worst-case time complexity for simple sorts like bubble and insertion sort?

O(n²).

Define a stable sorting algorithm.

A stable sorting algorithm maintains the relative order of records with equal keys (values).

Why is stability important in sorting?

It preserves the order of equal elements over multiple sorts, so sorting by one key doesn't disrupt the order of another key.

What is an in-place sorting algorithm?

An algorithm that requires only O(1) additional memory beyond the items being sorted (sometimes O(log n) is considered in-place).

What is a comparison sort?

A sort that examines data only by comparing two elements with a comparison operator.

Describe the basic idea of bubble sort.

Repeatedly step through the list, compare adjacent elements, and swap them if they are in the wrong order. The largest elements 'bubble' to the end.

In bubble sort, after the first full pass, where is the largest element guaranteed to be?

At the last position of the list.

How many passes does bubble sort need in the worst case for a list of n elements?

n-1 passes.

What is the main advantage of bubble sort?

It is simple to understand and implement, and it is stable.

Describe the basic idea of insertion sort.

Build the sorted list one element at a time by taking each new element and inserting it into its correct position among the already sorted elements.

In insertion sort, how does the algorithm find the correct position for an element?

It compares the element with those before it, shifting larger elements to the right until the correct spot is found.

What is the best-case time complexity of insertion sort and when does it occur?

O(n), when the list is already sorted.

Is insertion sort stable?

Yes, it is stable because equal elements retain their relative order.

Describe the basic idea of merge sort.

It is a divide-and-conquer algorithm that recursively splits the list into halves, sorts each half, and then merges the sorted halves back together.

What is the time complexity of merge sort in all cases (best, average, worst)?

O(n log n).

What is the main disadvantage of merge sort?

It requires additional memory for the temporary arrays used during merging, so it is not in-place.

Is merge sort stable?

Yes, merge sort is stable if implemented correctly.

Compare the number of comparisons in bubble sort vs. insertion sort in the worst case.

Both have O(n²) comparisons in the worst case, but insertion sort typically makes fewer comparisons in practice.

Which of the three sorts (bubble, insertion, merge) is generally the fastest for large lists?

Merge sort, because it has O(n log n) time complexity, while bubble and insertion are O(n²).

Which of the three sorts is an example of a divide-and-conquer algorithm?

Merge sort.

Unlock all 60 questions, flashcards & more

Create a free account to see every question, the slides, flashcards and revision notes for this topic.

Past papers

Past-paper practice for this topic is coming soon.

Coming soon