Lesson 06: Merge Sort
Specification Points Addressed in this lesson:
- Understand and explain how the merge sort algorithm works
- Compare and contrast merge sort and bubble sort algorithms.
Merging is one of the fundamental operations of the merge sort algorithm. Imagine you have two sorted lists; merging is the process of combining these two sorted lists into a single sorted list.
Steps to Merge Two Sorted Lists:
- Start by comparing the first item of both lists.
- Pick the smaller of the two values and place it into a new list.
- Move to the next item in the list from which you picked the smaller value and compare again.
- Repeat this process until you run out of items in one of the lists.
- Add the remaining items from the non-empty list to the new list.
2. Merge Sort
The merge sort algorithm can be understood in two main phases:
Phase 1: Splitting Phase
- Start with a list of n items.
- Repeatedly split the list into approximately halves until you have a collection of lists, each containing only one item.
- By the end of this phase, you have broken down the list into its most fundamental parts, which are inherently sorted.
Phase 2: Merging Phase
- Take the individual lists of single items and start merging them.
- First, merge pairs of single-item lists to form sorted lists of 2 items.
- Then, merge pairs of 2-item lists to form sorted lists of 4 items.
- Continue this doubling process, merging the sorted lists in order until you have a single sorted list of n items.
3. Comparing bubble sort and merge sort algorithm
The Bubble Sort Algorithm
Bubble sort, as the name suggests, “bubbles” larger values towards the end of the list in a series of passes. Here is how it works:
- Start at the beginning of the list.
- Compare two adjacent items. If they are out of order, swap them.
- Continue comparing and possibly swapping until the end of the list. This completes one pass.
- Repeat the passes until no more swaps are needed.
Advantages of bubble sort
- Do swaps in place; therefore, it requires less space.
- Most straightforward and easiest to code.
Disadvantages of bubble sort
- It requires many comparisons, and this number increases significantly with larger data sets.
- Slowest sorting method, especially on large unordered lists.
Advantages of merge sort
- Fastest sorting method, especially on large unordered lists.
Disadvantages of merge sort
- It requires a lot of space because it creates new lists during the merging phase.
- More difficult and complex to code compared to Bubble Sort.
Scenario: Nearly-Sorted List
Fastest Algorithm: Bubble Sort
- Bubble Sort is faster on a nearly-sorted list because it will detect the order quickly and require fewer passes.
- Merge Sort will always perform the same number of comparisons relative to the length of the list, regardless of the initial order of the list.
Scenario: Reverse-Order List
Fastest Algorithm: Merge Sort
- This represents the worst-case scenario for Bubble Sort, as it must perform the maximum number of swaps.
- Merge Sort’s behaviour remains consistent, always performing the same number of comparisons relative to the length of the list.
Scenario: Randomly Ordered List
Fastest Algorithm: Probably Merge Sort
- On average, and especially with larger data sets, Merge Sort tends to outperform Bubble Sort on a randomly ordered list due to its more efficient approach to organising data.
In summary, while Bubble Sort might have its moments of efficiency on nearly-sorted lists, Merge Sort generally offers a more reliable and faster method for sorting lists, especially large or unordered ones. However, this efficiency comes at the cost of space and coding complexity.