I. In-Class Exercises

Programming Exercises

1. Array Sort: L3111

II. Knowledge Summary

Core Idea

Merge sort is used to sort a collection of linearly stored data and is a classic sorting algorithm based on divide and conquer.

The core idea of merge sort is to break a large array into two smaller arrays. Then recursively sort these two smaller arrays, and finally merge the sorted smaller arrays into one large array. The efficiency of merge sort comes from its ability to merge two sorted arrays -- the merge operation can be completed in linear time.

Algorithm Principle

The three steps of merge sort:

1. Divide: Split the array to be sorted in half from the middle, until each subarray contains only one element (base case). A single element is naturally sorted.
2. Conquer: Recursively apply merge sort to these two subarrays until each part is sorted.
3. Combine: Merge the two sorted subarrays into one final sorted array. The merge process requires extra space to temporarily store both arrays, then selects elements from both arrays in order to fill the original array.

Example

Consider sorting the array [3, 1, 4, 1, 5, 9, 2, 6]:

Divide phase:

• [3, 1, 4, 1] and [5, 9, 2, 6]
• Further divided into [3, 1] and [4, 1], and [5, 9] and [2, 6]
• Finally divided into individual elements

Merge phase:

• Merge [3] and [1] to get [1, 3]
• Merge [4] and [1] to get [1, 4]
• Merge [1, 3] and [1, 4] to get [1, 1, 3, 4]
• Similarly, [5, 9] and [2, 6] merge to [2, 5, 6, 9]
• Finally, merge [1, 1, 3, 4] and [2, 5, 6, 9] to get [1, 1, 2, 3, 4, 5, 6, 9]

Code Implementation

Below is the complete implementation of merge sort, including the merge function and the recursive sort function:

1#include<iostream>
2#include<algorithm>
3#include<vector>
4#include "stdio.h"
5#include "time.h"
6using namespace std;
7
8int a[10000005] = {0};
9
10// Function to merge two sorted segments of the array
11void merge(int a[], int left, int mid, int right) {
12    int t[105] = {0}; // Create a temporary array to store the merged sorted sequence
13    int lp = left; // lp is the starting index of the left half
14    int rp = mid + 1; // rp is the starting index of the right half
15    int si = left; // si tracks the current insertion index in the temporary array t
16
17    // Traverse both halves until one reaches its end
18    while (si <= right) {
19        // If the left half is fully processed, or the right half's current element is smaller
20        if (lp > mid || (rp <= right && a[lp] > a[rp])) {
21            t[si] = a[rp]; // Copy the right half's current element to the temporary array
22            rp++; // Move the right half's index
23        }
24        else {
25            t[si] = a[lp]; // Otherwise, copy the left half's current element to the temporary array
26            lp++; // Move the left half's index
27        }
28        si++; // Move the temporary array's index
29    }
30
31    // Copy the sorted elements from the temporary array back to the original array a
32    for (int i = left; i <= right; i++) {
33        a[i] = t[i];
34    }
35}
36
37// Recursive implementation of merge sort
38void merge_sort(int a[], int left, int right) {
39    if (right <= left) {
40        return; // If the current segment has length 1 or 0, return directly
41    }
42    int mid = (left + right) / 2; // Find the midpoint to split the array in half
43    merge_sort(a, left, mid); // Recursively sort the left half
44    merge_sort(a, mid + 1, right); // Recursively sort the right half
45    merge(a, left, mid, right); // Merge the two sorted halves
46}
47
48int main() {
49        int n = 0;
50        cin >> n;
51        for (int i = 0; i < n; i++) {
52                cin >> a[i];
53        }
54        merge_sort(a, 0, n - 1);
55        for (int i = 0; i < n; i++) {
56                cout << a[i] << ' ';
57        }
58        cout << endl;
59        return 0;
60}

Execution Example

Using the array [5, 2, 8, 1, 9, 3] to demonstrate the complete recursive decomposition and merge process of merge sort:

Phase 1: Recursive Decomposition

1merge_sort([5, 2, 8, 1, 9, 3], 0, 5)
2├── merge_sort([5, 2, 8], 0, 2)       ← Left half
3│   ├── merge_sort([5, 2], 0, 1)
4│   │   ├── merge_sort([5], 0, 0)     ← Base case, return directly
5│   │   └── merge_sort([2], 1, 1)     ← Base case, return directly
6│   │   → merge([5], [2]) = [2, 5]    ★ Merge
7│   └── merge_sort([8], 2, 2)         ← Base case, return directly
8│   → merge([2, 5], [8]) = [2, 5, 8]  ★ Merge
9└── merge_sort([1, 9, 3], 3, 5)       ← Right half
10    ├── merge_sort([1, 9], 3, 4)
11    │   ├── merge_sort([1], 3, 3)     ← Base case, return directly
12    │   └── merge_sort([9], 4, 4)     ← Base case, return directly
13    │   → merge([1], [9]) = [1, 9]    ★ Merge
14    └── merge_sort([3], 5, 5)         ← Base case, return directly
15    → merge([1, 9], [3]) = [1, 3, 9]  ★ Merge
16→ merge([2, 5, 8], [1, 3, 9]) = [1, 2, 3, 5, 8, 9]  ★ Final merge

Phase 2: Detailed demonstration of the final merge

Merging [2, 5, 8] and [1, 3, 9]:

Algorithm Evaluation

The complexity and properties of merge sort are as follows:

• Time Complexity: O(n log n). Merge sort requires approximately log n decomposition steps, and each merge operation takes at most O(n) time. Whether best, worst, or average case, the time complexity is always O(n log n), which is a major advantage of merge sort.
• Space Complexity: O(n). The merge process requires an additional temporary array to store intermediate results.
• Stability: Stable sort. The relative order of equal elements is preserved after sorting, which is very important in certain applications.

Detailed Problem-Solving Steps

When using merge sort to solve problems:

1. Confirm the scenario: Merge sort is suitable for scenarios requiring stable sorting or needing to gather statistics during the merge process (e.g., counting inversions).
2. Write the decomposition function: Recursively split the array from the middle until each segment has only one element.
3. Write the merge function: This is the core of merge sort. Use two pointers pointing to the start of the left and right segments, each time taking the smaller element into the temporary array.
4. Remember to copy back to the original array: After merging, the sorted results in the temporary array need to be copied back to the corresponding positions in the original array.
5. Extended applications: When counting inversions, during the merge process, when a right element is smaller than a left element, all remaining left elements form inversions with it, allowing direct counting.

Common Mistakes

• Temporary array too small: The merge requires a temporary array that should be at least large enough to hold all elements of the current merge segment. The t[105] in the code should be adjusted based on the actual data size.
• Pointer out of bounds during merge: Before comparing a[lp] and a[rp], you must check whether lp and rp are already out of bounds. If one side is exhausted, directly take elements from the other side.
• Incorrect range when copying back to the original array: Should copy from left to right, not from 0 to right-left.
• Mid calculation: It is recommended to use mid = left + (right - left) / 2 instead of mid = (left + right) / 2, as the latter may cause integer overflow when left and right are large.
• Breaking stability: During merging, when elements from both sides are equal, you should take the left element first to preserve stability. Taking the right element first would disrupt the order of equal elements.

III. Homework

Programming Exercises

1. Word Sort: L3112