Recursive Merge Sort

Welcome to the lesson! In our previous session, we explored the concept of recursion, defining it by its two core components: a base case and a recursive step. We now have all the necessary building blocks to assemble one of the most efficient sorting algorithms.

Today, we will implement the full mergeSort algorithm. You will see how the "divide-and-conquer" strategy is perfectly realized through recursive function calls. By the end of this lesson, you will have written the mergeSort function in C, combining the power of recursion with the merge helper function we've already designed.

1. The Recursive Logic of Merge Sort

Recall that Merge Sort works by:

1. Divide: Breaking the array into two halves.
2. Conquer: Recursively sorting each half.
3. Combine: Merging the two sorted halves back into one sorted array.

Recursion is the mechanism that drives the "conquer" step. The process continues until the arrays can't be divided any further. This gives us the two critical components for our recursive function:

• Base Case: An array with one or zero elements is, by definition, already sorted. This is our stopping condition. In terms of array indices left and right, this occurs when left >= right.
• Recursive Step: If the array has more than one element (left < right), we:
  1. Calculate the middle index mid.
  2. Call mergeSort on the left half (from left to mid).
  3. Call mergeSort on the right half (from mid + 1 to right).
  4. Call our merge function to combine the two (now sorted) halves.

The following diagram provides a fantastic overview of this entire process, from the initial division down to single elements to the final merging sequence.

2. Implementing the mergeSort Function in C

With the logic clear, let's translate it into a C function. The mergeSort function will orchestrate the recursive calls. Its main job is to keep splitting the array until it hits the base case, at which point the merge function begins its work on the way back up the call stack.

Let's study the C code for the main mergeSort function.

To see this code being constructed and explained live, the following video provides a great walkthrough.

3. Tracing the Execution Flow

To truly understand how recursion works here, it's helpful to trace the sequence of function calls. The function first calls itself all the way down one branch (the left side) until it hits the base case. Then it backs up, completes the other branch (the right side), and performs a merge. This repeats until the entire array is sorted.

The following video provides one of the clearest traces available for how the indices change and how the array is processed.

4. Hands-on Practice: Bringing It All Together

Now it's time to assemble the complete program and see it run. The code below includes the main function, our new mergeSort function, and the merge function from our previous work.

Your task is to add printf statements to trace the execution yourself. This is a powerful debugging and learning technique that makes the abstract flow of recursion visible.

#include <stdio.h>

// Merges two subarrays of arr[].
// First subarray is arr[p..q]
// Second subarray is arr[q+1..r]
void merge(int arr[], int p, int q, int r) {
    // Create temporary arrays
    int n1 = q - p + 1;
    int n2 = r - q;
    int L[n1], M[n2];

    // Copy data to temp arrays L[] and M[]
    for (int i = 0; i < n1; i++)
        L[i] = arr[p + i];
    for (int j = 0; j < n2; j++)
        M[j] = arr[q + 1 + j];

    // Merge the temp arrays back into arr[p..r]
    int i = 0; // Initial index of first subarray
    int j = 0; // Initial index of second subarray
    int k = p; // Initial index of merged subarray

    while (i < n1 && j < n2) {
        if (L[i] <= M[j]) {
            arr[k] = L[i];
            i++;
        } else {
            arr[k] = M[j];
            j++;
        }
        k++;
    }

    // Copy the remaining elements of L[], if there are any
    while (i < n1) {
        arr[k] = L[i];
        i++;
        k++;
    }

    // Copy the remaining elements of M[], if there are any
    while (j < n2) {
        arr[k] = M[j];
        j++;
        k++;
    }
    // Task Part 2: Add a printf here to see when merging happens.
    printf("--- Merged subarray from %d to %d ---\n", p, r);
}

// Main function to implement merge sort
void mergeSort(int arr[], int l, int r) {
    if (l < r) {
        // Task Part 1: Add a printf here to trace the division.
        printf("Splitting array from index %d to %d\n", l, r);
        
        int m = l + (r - l) / 2;

        mergeSort(arr, l, m);
        mergeSort(arr, m + 1, r);

        merge(arr, l, m, r);
    }
}

// Function to print an array
void printArray(int arr[], int size) {
    for (int i = 0; i < size; i++)
        printf("%d ", arr[i]);
    printf("\n");
}

// Driver program to test above functions
int main() {
    int arr[] = {6, 5, 12, 10, 9, 1};
    int arr_size = sizeof(arr) / sizeof(arr[0]);

    printf("Given array is \n");
    printArray(arr, arr_size);

    mergeSort(arr, 0, arr_size - 1);

    printf("\nSorted array is \n");
    printArray(arr, arr_size);
    return 0;
}

Your Task:

1. Copy the code into your development environment.
2. Add a printf statement at the beginning of the mergeSort function to show the l (left) and r (right) indices. This will show you each time the array is "split."
3. Add another printf at the end of the merge function to announce which subarray has just been merged.
4. Compile and run the program.
5. Compare the output trace to the tree diagram we saw earlier. You should see the Splitting... messages correspond to the downward paths of the tree, and the Merged... messages correspond to the upward, combining paths.

Conclusion

Congratulations! You have successfully implemented the mergeSort algorithm in C. By combining the power of recursion with a clever merging strategy, we've created a highly efficient sorting algorithm from the ground up.

Key Takeaways:

• The mergeSort function uses recursion to implement the "divide and conquer" strategy.
• The base case for the recursion is a subarray of size 1 or 0 (l >= r), which is inherently sorted.
• The recursive step involves finding the midpoint, calling mergeSort on both halves, and then calling merge to combine the results.
• Tracing the execution with printf statements is a practical way to visualize the call stack and understand the algorithm's flow.

Preview of the Next Lesson:
Now that we've implemented four sorting algorithms (Bubble, Selection, Insertion, and Merge Sort), how do they stack up against each other? In our next lesson, we will analyze the time and space complexity of Merge Sort, formally proving its O(n log n) efficiency. We will then compare the performance characteristics of all the sorting algorithms covered so far to understand when to use each one.