Standard Sorting Algorithms

Sorting algorithms are used to arrange the elements of a list in a specific order, usually ascending or descending. The three standard sorting algorithms you need to know are Bubble Sort, Merge Sort, and Insertion Sort.

Bubble Sort

Bubble Sort compares adjacent items in the list and swaps them if they are in the wrong order. This process continues through the list until all the items are sorted.

Method

Start by comparing the first two items in the list.
If they are out of order, swap them.
Move to the next pair (items 2 and 3) and repeat step 2.
Continue until you reach the end of the list.
Repeat the process for all items until no more swaps are needed (i.e., the list is sorted).

Worked Example

In the image below, the list is gradually sorted as adjacent items are compared and swapped when necessary. Blue indicates items being compared, and red shows the final sorted item.

infoNote

Starting on the left, the pairs of items are compared and swapped if needed (in blue). We then move to the next pair and repeat until we get to the end of the list.

This is the first pass. The largest item will be at the end of the list after the first pass.

Red indicates the item is sorted.

This is repeated until all items are in order.

infoNote

Key Points

Simple to implement but inefficient for large lists.
Best used when the list is small or nearly sorted.
Requires n-1 passes for a list of length n.

Merge Sort

Merge Sort is a divide-and-conquer algorithm that splits a list into smaller sub-lists until each sub-list contains a single item. It then merges the sub-lists back together in order.

Method

Divide the list into two halves.
Repeat this process until each sub-list has only one item.
Merge the sub-lists, sorting them as you go.
Continue merging until the entire list is sorted.

Worked Example

The image below shows how the list is split into sub-lists and then merged in order until the entire list is sorted.

infoNote

The list is split in half and this is repeated until you have sub-lists with only 1 item. The pairs of sub-lists are then merged together in order.

This is repeated until they are all merged in order

infoNote

Key Points

Efficient for large lists.
Requires extra memory to store the sub-lists.
Ideal for data that needs to be sorted quickly.

Insertion Sort

Insertion Sort builds the sorted list one item at a time by repeatedly taking the next unsorted item and inserting it into the correct position.

Method

Start with the second item in the list.
Compare it with the items before it and insert it into its correct position.
Move to the next item and repeat the process until the whole list is sorted.

Worked Example

In the image, each red item is inserted into its correct position within the grey sorted portion of the list.

infoNote

Each item is taken in turn starting from the left. The red item is taken and inserted into the correct position on the left side of the list.

You have 2 lists:

The unsorted list to the right
The sorted list to the left of the item. You repeat the steps until it is sorted

infoNote

Key Points

More efficient than Bubble Sort on small or nearly sorted lists.
Uses less memory than Merge Sort.
Simple to implement, but slow on large lists.

Comparing Bubble Sort, Merge Sort, and Insertion Sort

Bubble Sort	Merge Sort	Insertion Sort
Compares pairs of items and swaps if needed.	Divides list into smaller sub-lists, then merges in order.	Inserts each item into its correct place.
Inefficient for large lists.	Efficient for large lists.	More efficient than Bubble Sort for small, nearly sorted lists.
Simple but slow.	Requires extra memory.	Uses less memory than Merge Sort.
Suitable for small, unsorted lists.	Best for large datasets.	Best for small, nearly sorted lists.

infoNote

Key Points to Remember

Bubble Sort is the slowest and simplest, mostly used for small datasets or when checking if a list is already sorted.
Merge Sort is the fastest and most efficient for large datasets but requires extra memory.
Insertion Sort works well for small datasets or lists that are nearly sorted, using less memory than Merge Sort.

Standard Sorting Algorithms Simplified Revision Notes for GCSE OCR Computer Science

Standard Sorting Algorithms

Bubble Sort

Method

Worked Example

Key Points

Merge Sort

Method

Worked Example

Key Points

Insertion Sort

Method

Worked Example

Key Points

Comparing Bubble Sort, Merge Sort, and Insertion Sort

Key Points to Remember

500K+ Students Use These Powerful Tools to Master Standard Sorting Algorithms For their GCSE Exams.

Other Revision Notes related to Standard Sorting Algorithms you should explore