I. In-Class Exercises

Programming Exercises

1. Array Sorting: 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 split a large array into two smaller arrays to solve. It then recursively sorts the two smaller arrays and finally merges the sorted smaller arrays into a single 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 from the middle into two parts, until each subarray contains only one element (the base case). A single element is naturally sorted and requires no sorting.
2. Conquer: Recursively apply merge sort to these two subarrays until each subpart is sorted.
3. Combine: Merge the two sorted subarrays into a single final sorted array. The merge process requires extra space to temporarily store the two arrays, then elements are selected in order from both arrays to fill back into 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 into [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

Here 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 subarrays
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 is exhausted
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] as an example, here is the complete merge sort recursive decomposition and merge process:

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 view of the last merge

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

✨ Algorithm Evaluation

The complexity and characteristics 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 case, worst case, 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 remains unchanged 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 that require stable sorting or need to use the merge process to gather statistics (such as 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 respectively, and each time take 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 elements on the left form inversions with it, and can be counted directly.

✨ Common Mistakes

• Temporary array too small: The merge requires a temporary array whose size should be at least large enough to hold all elements in the current merge segment. The t[105] in the code should be adjusted according to the actual data size.
• Pointer out of bounds during merge: Before comparing a[lp] and a[rp], you must first check whether lp and rp have gone out of bounds. If one side is exhausted, elements should be taken directly from the other side.
• Wrong range when copying back to the original array: The copy should go from left to right, not from 0 to right-left.
• Calculating mid: 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 very large.
• Breaking stability: During merging, when elements on both sides are equal, the left element should be taken first to maintain stability. If the right element is taken first, the order of equal elements will be disrupted.

III. Homework

Programming Exercises

1. Word Sorting: L3112