## 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:**

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

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