Merge Sort
Computer Science: OCR A Level, topic 8.1.7
Merge Sort
Merge sort is an example of a divide and conquer algorithm, where the problem is broken down into smaller steps.
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
- 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.
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