Seneca
Sign up

Merge Sort

Computer Science: OCR GCSE, topic 2.1.14

Merge Sort

Merge sort is an example of a divide and conquer algorithm, where the problem is broken down into smaller steps.

The concept

The concept

  • If we have two packs of cards, which are both already in order and want to combine them, what can we do?
  • One solution is to only consider the top card of each pile, and create a new deck starting from the smaller of the two cards.
  • This will give us a combined sorted pack.
  • This is called merge sort.
In English

In English

  • Split the lists into lists of size one.
  • Merge each pair of sublists by comparing the first value of each list and putting the smaller value into the new list first.
  • Continue merging until there is only one list.
  • It is always the first two items of two adjacent lists that are being compared.
  • Some lists may end up one-sided, where many more numbers in one list are compared with fewer numbers in another for the final merge. That is ok! The lists do not always need to remain balanced.
Example

Example

  • We will sort the list [12, 5, 9, 1] using merge sort.
  • Step 1: Split the list until each piece has one element
  • Step 2: Merge [12] and [5]
  • 5 < 12 → 5 'comes down'
  • Step 3: Merge [12] and [ ]
  • 12 'comes down'
  • Step 4: Merge [9] and [1]
  • 1 'comes down'
  • Step 5: Merge [9] and [ ]
  • 9 'comes down'
  • Step 6: Merge [5, 12] and [1, 9]
  • Compare first items
  • 5 > 1
  • 1 'comes down'
  • Step 7: Compare first items
  • 5 < 9
  • 5 'comes down'
  • Step 8: Compare first items
  • 12 > 9
  • 9 'comes down'
  • Step 9:
  • 12 comes down
Pros and cons of merge sort:

Pros and cons of merge sort:

  • Pros:
  • A very efficient algorithm.
  • Cons:
  • Can be slower for small lists.
  • Needs additional memory.

Test yourself on Merge Sort

  • When is it a particularly bad idea to use merge sort?

  • Merge Sort in English

Practise this topic for free