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.

1. Merging

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:

1. Start by comparing the first item of both lists.
2. Pick the smaller of the two values and place it into a new list.
3. Move to the next item in the list from which you picked the smaller value and compare again.
4. Repeat this process until you run out of items in one of the lists.
5. 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:

1. Start at the beginning of the list.
2. Compare two adjacent items. If they are out of order, swap them.
3. Continue comparing and possibly swapping until the end of the list. This completes one pass.
4. 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.

Comparison Scenarios:

Scenario: Nearly-Sorted List

Fastest Algorithm: Bubble Sort

Explanation:

• 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

Explanation:

• 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

Explanation:

• 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.