Implementing Merge for Sorted Arrays

Welcome back! In our last lesson, we introduced the powerful Divide and Conquer strategy and saw how Merge Sort uses it to approach sorting more efficiently than the $O(n^2)$ algorithms we studied earlier. We learned that Merge Sort works by recursively dividing an array into single-element subarrays and then merging them back together in sorted order.

Today, we're going to zoom in on the most crucial part of this process: the "merge" step. Our goal is to implement the merge helper function, which takes two already sorted arrays and combines them into a single, final sorted array. Mastering this function is the key to unlocking the power of Merge Sort.

1. The Logic of Merging

Imagine you have two decks of cards, each sorted by number. How would you combine them into a single sorted deck? You'd likely place both decks face up, compare the top card of each deck, take the smaller one, and place it on your new pile. You'd repeat this until one deck is empty, and then you'd simply place the rest of the other deck on top of your new pile.

This is exactly the logic of the merge algorithm. We use three pointers, or indices, to keep track of our position:

• An index i for the first sorted array.
• An index j for the second sorted array.
• An index k for the final, merged array.

We compare the elements at i and j, copy the smaller one to position k in the result, and advance the appropriate indices.

This process is illustrated beautifully in the following diagram.

2. A Simple Implementation: Merging Two Separate Arrays

Let's start by implementing the simplest version of this logic: a function that takes two separate, sorted arrays and merges them into a third, newly created array. This will help us solidify the core algorithm before we adapt it for the specific needs of Merge Sort.

The following video provides an excellent walkthrough of creating such a function in C.

After watching, the core structure of the C code should be clear. It consists of three main parts:

1. A while loop that compares elements from both arrays and copies the smaller one.
2. A while loop to copy any remaining elements from the first array.
3. A while loop to copy any remaining elements from the second array.

3. Adapting the merge Function for Merge Sort

In the context of the full Merge Sort algorithm, we aren't merging two completely separate arrays. Instead, we are merging two adjacent, sorted subarrays that exist within a single, larger array.

For example, if our main array is arr = {2, 8, 1, 7}, after the first recursive calls, it might look like arr = {2, 8, 1, 7} but we conceptually treat arr[0...1] (which is {2, 8}) and arr[2...3] (which is {1, 7}) as two separate sorted subarrays that need to be merged. The goal is to merge them back into the original array arr so it becomes {1, 2, 7, 8} in the range [0...3].

To do this without losing data (since we are writing back into the same array we are reading from), we must first copy the two subarrays into temporary helper arrays. Then, we can use our merging logic to place the elements from these temporary arrays back into the original array in sorted order.

The following article provides an excellent C implementation and a step-by-step visual guide.

4. Code Breakdown and Practice

Let's consolidate what you've learned into a complete, runnable C program. The code below contains the merge function as described in the Programiz article, along with a main function to test it.

#include <stdio.h>

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

// 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) {
    // 1. Calculate sizes and create temporary arrays
    int n1 = q - p + 1;
    int n2 = r - q;

    int L[n1], M[n2];

    // 2. Copy data from the main array to temporary 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];

    // 3. Merge the temporary 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

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

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

    // 5. Copy the remaining elements of M[], if there are any
    while (j < n2) {
        arr[k] = M[j];
        j++;
        k++;
    }
}

int main() {
    // Create an array with two sorted subarrays: {1, 5, 10} and {2, 6, 9}
    int arr[] = {1, 5, 10, 2, 6, 9};
    int size = sizeof(arr) / sizeof(arr[0]);

    // Define the indices for the merge function:
    // p = 0 (start of first subarray)
    // q = 2 (end of first subarray)
    // r = 5 (end of second subarray)
    int p = 0;
    int q = 2;
    int r = 5;

    printf("Original array: \n");
    printArray(arr, size);

    merge(arr, p, q, r);

    printf("Array after merge: \n");
    printArray(arr, size);

    return 0;
}

Your Task:

1. Copy this code into your development environment.
2. Compile and run it. Verify that the output is a single sorted array: 1 2 5 6 9 10.
3. Experiment! Change the values in arr to test other cases. For example, try int arr[] = {4, 8, 12, 1, 3, 5}; and see if it works correctly. Make sure the subarrays you create are individually sorted.

This hands-on exercise is crucial for confirming your understanding of how the function operates on the underlying array data.

Conclusion

In this lesson, we dissected the core mechanism of Merge Sort. You've now built the engine that drives this efficient algorithm.

Key Takeaways:

• The merge operation combines two sorted arrays by iteratively comparing their elements and picking the smaller one.
• The logic relies on three indices: one for each input array and one for the output array.
• When used in Merge Sort, we merge adjacent subarrays. This requires creating temporary arrays to hold the data before merging it back into the original array.
• The C implementation involves four key parts: creating and populating temporary arrays, a main comparison loop, and two cleanup loops for any leftover elements.

Preview of the Next Lesson:
We now have the merge helper function ready. The next step is to build the mergeSort function that orchestrates the "divide" part of the strategy. To do that, we first need to formally understand and practice recursion, the technique of a function calling itself. In the next lesson, we will dive into recursion and then use it to complete our implementation of Merge Sort.