Merging two sorted arrays into a single sorted array

In the previous article, we explored the high-level idea behind Merge Sort and how it uses a divide-and-conquer strategy to sort a list efficiently. At the core of this algorithm is a basic but very important operation: merging two sorted arrays into a single sorted array. This operation is not only fundamental to Merge Sort but also a useful technique in many real-world applications. Let’s dive into the intuition behind merging two sorted arrays and understand why it’s so efficient.

The Problem: Merging Two Sorted Lists

Imagine you have two stacks of numbered cards, and each stack is already sorted in ascending order. Your goal is to combine these two stacks into a single, sorted stack. How would you approach this? Intuitively, you’d compare the top cards of both stacks, pick the smaller one, and place it in the new stack. You’d repeat this process until all the cards are merged. This is the essence of merging two sorted arrays.

Algorithm to Merge Two Sorted Lists Efficiently

Below is the algorithm to efficiently merge two sorted lists into a single sorted list:

1. Start at the Beginning: Begin by looking at the first element of each array. Compare these two elements.

2. Pick the Smaller Element: The smaller of the two elements is guaranteed to be the smallest element in the combined array. Add it to the result.

3. Move Forward: Move to the next element in the array from which you just picked the smaller element. Compare it with the current element of the other array.

4. Repeat Until Done: Continue this process until you’ve exhausted all elements in one of the arrays. Then, simply add the remaining elements from the other array to the result.

This approach is efficient because you don’t need to compare every element with every other element. Instead, you only compare the smallest/largest value from each sorted array and move one of it to the sorted array.

Example Walkthrough of Merge Algorithm

Let’s say you have two sorted arrays:

Here’s how the merging process would unfold:

1. Compare 3 (from A) and 2 (from B). Since 2 is smaller, add it to the result. Result: [2].
2. Compare 3 (from A) and 5 (from B). Since 3 is smaller, add it to the result. Result: [2, 3].
3. Compare 7 (from A) and 5 (from B). Since 5 is smaller, add it to the result. Result: [2, 3, 5].
4. Compare 7 (from A) and 8 (from B). Since 7 is smaller, add it to the result. Result: [2, 3, 5, 7].
5. Compare 10 (from A) and 8 (from B). Since 8 is smaller, add it to the result. Result: [2, 3, 5, 7, 8].
6. Now, Array B is exhausted. Simply add the remaining elements from Array A ([10]) to the result. Final result: [2, 3, 5, 7, 8, 10].

Implementation the Algorithm to Merge Two Sorted Arrays

Below is the implementation of the algorithm to merge two sorted arrays into a single sorted array:

Time and Space Complexity

The time complexity of merging two sorted arrays is O(n + m), where n and m are the sizes of the two arrays being merged. This is because, on an average you would compare each element in both the arrays once.

The space complexity of the merge operation is also O(n + m) because you need to create a new array to store the merged result. This additional space is required to hold the combined elements of both input arrays.

In summary:

• Time Complexity: O(n + m)
• Space Complexity: O(n + m)

In the next article, we’ll explore how the merge routine fits into the Merge Sort algorithm and how it uses recursion to sort an entire array.