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:
Start at the Beginning: Begin by looking at the first element of each array. Compare these two elements.
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.
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.
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:
Compare 3 (from A) and 2 (from B). Since 2 is smaller, add it to the result. Result: [2].
Compare 3 (from A) and 5 (from B). Since 3 is smaller, add it to the result. Result: [2, 3].
Compare 7 (from A) and 5 (from B). Since 5 is smaller, add it to the result. Result: [2, 3, 5].
Compare 7 (from A) and 8 (from B). Since 7 is smaller, add it to the result. Result: [2, 3, 5, 7].
Compare 10 (from A) and 8 (from B). Since 8 is smaller, add it to the result. Result: [2, 3, 5, 7, 8].
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:
def merge_sorted_lists(list1, list2):
# Initialize empty result list and pointers for both input lists
# i tracks position in list1 and starts from position 0
# j tracks position in list2 and starts from position 0
merged = []
i = j = 0
# Process both lists until we reach the end of either one
# Compare elements at current positions and add the smaller one to result
while i < len(list1) and j < len(list2):
if list1[i] <= list2[j]:
# If list1's element is smaller/equal
# add it to the result and move list1's pointer
merged.append(list1[i])
i += 1
else:
# If list2's element is smaller
# add it to the result and move list2's pointer
merged.append(list2[j])
j += 1
# At this point, at least one list is fully processed
# Now we need to handle any remaining elements
# If there are remaining elements in list1, add them all
# This happens when list2 is fully processed but list1 still has elements
while i < len(list1):
merged.append(list1[i])
i += 1
# If there are remaining elements in list2, add them all
# This happens when list1 is fully processed but list2 still has elements
while j < len(list2):
merged.append(list2[j])
j += 1
return merged
# Example usage with test arrays
list1 = [3, 7, 10] # First sorted input list
list2 = [2, 5, 8] # Second sorted input list
result = merge_sorted_lists(list1, list2)
print(f"Input list1: {list1}")
print(f"Input list2: {list2}")
print(f"Merged sorted output: {result}")
#include <stdio.h>
#include <stdlib.h>
// Function to merge two sorted arrays into one sorted array
int* merge_sorted_lists(int* list1, int list1_size, int* list2, int list2_size, int* result_size) {
// Initialize empty result array and pointers for both input lists
// i tracks position in list1 and starts from position 0
// j tracks position in list2 and starts from position 0
*result_size = list1_size + list2_size;
int* merged = (int*)malloc(*result_size * sizeof(int));
int i = 0, j = 0, k = 0;
// Process both lists until we reach the end of either one
// Compare elements at current positions and add the smaller one to result
while (i < list1_size && j < list2_size) {
if (list1[i] <= list2[j]) {
// If list1's element is smaller/equal
// add it to the result and move list1's pointer
merged[k++] = list1[i++];
} else {
// If list2's element is smaller
// add it to the result and move list2's pointer
merged[k++] = list2[j++];
}
}
// At this point, at least one list is fully processed
// Now we need to handle any remaining elements
// If there are remaining elements in list1, add them all
// This happens when list2 is fully processed but list1 still has elements
while (i < list1_size) {
merged[k++] = list1[i++];
}
// If there are remaining elements in list2, add them all
// This happens when list1 is fully processed but list2 still has elements
while (j < list2_size) {
merged[k++] = list2[j++];
}
return merged;
}
// Helper function to print an array
void print_array(int* arr, int size) {
printf("[");
for (int i = 0; i < size; i++) {
printf("%d", arr[i]);
if (i < size - 1) {
printf(", ");
}
}
printf("]\n");
}
int main() {
// Example usage with test arrays
int list1[] = {3, 7, 10}; // First sorted input list
int list1_size = sizeof(list1) / sizeof(list1[0]);
int list2[] = {2, 5, 8}; // Second sorted input list
int list2_size = sizeof(list2) / sizeof(list2[0]);
int result_size;
int* result = merge_sorted_lists(list1, list1_size, list2, list2_size, &result_size);
printf("Input list1: ");
print_array(list1, list1_size);
printf("Input list2: ");
print_array(list2, list2_size);
printf("Merged sorted output: ");
print_array(result, result_size);
// Free the allocated memory for the result array
free(result);
return 0;
}
#include <iostream>
#include <vector>
using namespace std;
// Function to merge two sorted vectors into one sorted vector
vector<int> merge_sorted_lists(const vector<int>& list1, const vector<int>& list2) {
// Initialize empty result vector and pointers for both input vectors
// i tracks position in list1 and starts from position 0
// j tracks position in list2 and starts from position 0
vector<int> merged;
int i = 0, j = 0;
// Process both vectors until we reach the end of either one
// Compare elements at current positions and add the smaller one to result
while (i < list1.size() && j < list2.size()) {
if (list1[i] <= list2[j]) {
// If list1's element is smaller/equal
// add it to the result and move list1's pointer
merged.push_back(list1[i]);
i++;
} else {
// If list2's element is smaller
// add it to the result and move list2's pointer
merged.push_back(list2[j]);
j++;
}
}
// At this point, at least one vector is fully processed
// Now we need to handle any remaining elements
// If there are remaining elements in list1, add them all
// This happens when list2 is fully processed but list1 still has elements
while (i < list1.size()) {
merged.push_back(list1[i]);
i++;
}
// If there are remaining elements in list2, add them all
// This happens when list1 is fully processed but list2 still has elements
while (j < list2.size()) {
merged.push_back(list2[j]);
j++;
}
return merged;
}
int main() {
// Example usage with test vectors
vector<int> list1 = {3, 7, 10}; // First sorted input vector
vector<int> list2 = {2, 5, 8}; // Second sorted input vector
vector<int> result = merge_sorted_lists(list1, list2);
// Print input and output
cout << "Input list1: ";
for (int num : list1) {
cout << num << " ";
}
cout << endl;
cout << "Input list2: ";
for (int num : list2) {
cout << num << " ";
}
cout << endl;
cout << "Merged sorted output: ";
for (int num : result) {
cout << num << " ";
}
cout << endl;
return 0;
}
// Function to merge two sorted arrays into one sorted array
function mergeSortedLists(list1, list2) {
// Initialize empty result array and pointers for both input arrays
// i tracks position in list1 and starts from position 0
// j tracks position in list2 and starts from position 0
let merged = [];
let i = 0;
let j = 0;
// Process both arrays until we reach the end of either one
// Compare elements at current positions and add the smaller one to result
while (i < list1.length && j < list2.length) {
if (list1[i] <= list2[j]) {
// If list1's element is smaller/equal
// add it to the result and move list1's pointer
merged.push(list1[i]);
i++;
} else {
// If list2's element is smaller
// add it to the result and move list2's pointer
merged.push(list2[j]);
j++;
}
}
// At this point, at least one array is fully processed
// Now we need to handle any remaining elements
// If there are remaining elements in list1, add them all
// This happens when list2 is fully processed but list1 still has elements
while (i < list1.length) {
merged.push(list1[i]);
i++;
}
// If there are remaining elements in list2, add them all
// This happens when list1 is fully processed but list2 still has elements
while (j < list2.length) {
merged.push(list2[j]);
j++;
}
return merged;
}
// Example usage with test arrays
let list1 = [3, 7, 10]; // First sorted input array
let list2 = [2, 5, 8]; // Second sorted input array
let result = mergeSortedLists(list1, list2);
console.log(`Input list1: ${list1}`);
console.log(`Input list2: ${list2}`);
console.log(`Merged sorted output: ${result}`);
// Java code for merging two sorted lists
import java.util.ArrayList;
import java.util.List;
public class Main {
public static List<Integer> mergeSortedLists(List<Integer> list1, List<Integer> list2) {
// Initialize empty result list and pointers for both input lists
// i tracks position in list1 and starts from position 0
// j tracks position in list2 and starts from position 0
List<Integer> merged = new ArrayList<>();
int i = 0, j = 0;
// Process both lists until we reach the end of either one
// Compare elements at current positions and add the smaller one to result
while (i < list1.size() && j < list2.size()) {
if (list1.get(i) <= list2.get(j)) {
// If list1's element is smaller/equal
// add it to the result and move list1's pointer
merged.add(list1.get(i));
i++;
} else {
// If list2's element is smaller
// add it to the result and move list2's pointer
merged.add(list2.get(j));
j++;
}
}
// At this point, at least one list is fully processed
// Now we need to handle any remaining elements
// If there are remaining elements in list1, add them all
// This happens when list2 is fully processed but list1 still has elements
while (i < list1.size()) {
merged.add(list1.get(i));
i++;
}
// If there are remaining elements in list2, add them all
// This happens when list1 is fully processed but list2 still has elements
while (j < list2.size()) {
merged.add(list2.get(j));
j++;
}
return merged;
}
public static void main(String[] args) {
// Example usage with test arrays
List<Integer> list1 = new ArrayList<>();
list1.add(3);
list1.add(7);
list1.add(10); // First sorted input list
List<Integer> list2 = new ArrayList<>();
list2.add(2);
list2.add(5);
list2.add(8); // Second sorted input list
List<Integer> result = mergeSortedLists(list1, list2);
System.out.println("Input list1: " + list1);
System.out.println("Input list2: " + list2);
System.out.println("Merged sorted output: " + result);
}
}
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.