Published: 7 May 2025 | Reading Time: 6 minutes
Merge K Sorted Arrays is a fundamental problem in computer science, frequently encountered in technical interviews and real-world applications. This problem arises in scenarios such as database management, data compression, and information retrieval, where efficiently handling sorted data is crucial for performance.
This guide explores various approaches to solving the problem of merging K sorted arrays, including the brute-force method, min heap approach, and divide-and-conquer technique, with detailed analysis of their time complexity, space requirements, and practical applications.
The task is to merge K sorted arrays, each containing N elements, into a single sorted array. The key challenge lies in efficiently sorting elements from multiple arrays while keeping track of their positions.
When merging multiple sorted arrays, we need to ensure that the final merged array maintains a sorted order without performing unnecessary computations. The naive approach of concatenating all arrays and sorting them is inefficient, especially for large values of K and N. Therefore, an optimized approach is required to handle the merging process efficiently.
K = 3, N = 4
arr1 = [1, 3, 5, 7]
arr2 = [2, 4, 6, 8]
arr3 = [0, 9, 10, 11]
Start with the three sorted arrays:
[1, 3, 5, 7]
[2, 4, 6, 8]
[0, 9, 10, 11]
Merge the first two arrays:
[1, 3, 5, 7] + [2, 4, 6, 8] → [1, 2, 3, 4, 5, 6, 7, 8]
Merge the result with the third array:
[1, 2, 3, 4, 5, 6, 7, 8] + [0, 9, 10, 11] → [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11]
[0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11]
When merging multiple sorted arrays into a single sorted array, we can follow different strategies to achieve the goal efficiently. This section explores three main approaches: Brute-Force, Min Heap, and Divide and Conquer.
The Brute-Force Approach is the simplest method for merging K sorted arrays. It follows these steps:
This approach ensures correctness but is not the most efficient, as sorting takes additional time.
def merge_k_sorted_arrays(arrays):
result = [] # Step 1: Initialize an empty list
for array in arrays:
result.extend(array) # Step 2: Add all elements from each array
result.sort() # Step 3: Sort the combined list
return result # Step 4: Return the sorted list
# Example usage
arrays = [[1, 3, 5], [2, 4], [0]]
print(merge_k_sorted_arrays(arrays))
resultextend() to append all elements to the resultsort() to order them in non-decreasing order[0, 1, 2, 3, 4, 5]
The Min Heap Approach efficiently merges K sorted arrays by maintaining a min heap (priority queue) to extract the smallest element at each step. This significantly improves performance over the brute-force method.
import heapq
def merge_k_sorted_arrays(arrays):
min_heap = []
result = []
# Step 1: Insert the first element of each array into the heap
for i in range(len(arrays)):
if arrays[i]: # Ensure array is not empty
heapq.heappush(min_heap, (arrays[i][0], i, 0)) # (value, array index, element index)
# Step 2: Extract min and push the next element from the same array
while min_heap:
val, arr_idx, elem_idx = heapq.heappop(min_heap) # Get the smallest element
result.append(val)
# Step 3: Insert the next element from the same array into the heap
if elem_idx + 1 < len(arrays[arr_idx]):
heapq.heappush(min_heap, (arrays[arr_idx][elem_idx + 1], arr_idx, elem_idx + 1))
return result
# Example usage
arrays = [[1, 3, 5], [2, 4, 6], [0, 9, 10]]
print(merge_k_sorted_arrays(arrays))
min_heap) to keep track of the smallest elements from each arrayheappop), add it to the result list, and then push the next element from the same array into the heap[0, 1, 2, 3, 4, 5, 6, 9, 10]
The Divide and Conquer Approach efficiently merges K sorted arrays by recursively splitting them into smaller groups, merging them pairwise, and combining them step by step. This approach leverages the efficiency of Merge Sort to achieve optimal performance.
def merge_two_sorted_arrays(arr1, arr2):
""" Helper function to merge two sorted arrays """
i, j = 0, 0
merged = []
while i < len(arr1) and j < len(arr2):
if arr1[i] < arr2[j]:
merged.append(arr1[i])
i += 1
else:
merged.append(arr2[j])
j += 1
# Append remaining elements
while i < len(arr1):
merged.append(arr1[i])
i += 1
while j < len(arr2):
merged.append(arr2[j])
j += 1
return merged
def merge_k_sorted_arrays(arrays, left, right):
""" Recursively merges K sorted arrays using divide and conquer """
if left == right:
return arrays[left]
mid = (left + right) // 2
left_half = merge_k_sorted_arrays(arrays, left, mid)
right_half = merge_k_sorted_arrays(arrays, mid + 1, right)
return merge_two_sorted_arrays(left_half, right_half)
# Wrapper function
def merge_k_arrays(arrays):
if not arrays:
return []
return merge_k_sorted_arrays(arrays, 0, len(arrays) - 1)
# Example usage
arrays = [[1, 3, 5], [2, 4, 6], [0, 9, 10], [8, 12, 15]]
print(merge_k_arrays(arrays))
The function first merges two sorted arrays using a two-pointer approach. It then recursively divides the list of arrays into two halves until only one array remains. The left and right halves are merged step by step until all arrays are combined.
A wrapper function handles the input and starts the merging process. The approach ensures efficient sorting with O(KN log K) time complexity.
[0, 1, 2, 3, 4, 5, 6, 8, 9, 10, 12, 15]
Merge K Sorted Arrays is a common problem in computer science with applications in databases, information retrieval, and big data processing. Various approaches can be used to solve this problem, each with different efficiency levels.
The Brute-Force Approach is simple but inefficient, while the Min Heap Approach improves performance by using a priority queue. The Divide and Conquer Approach further optimizes the process by reducing the number of comparisons.
Choosing the right approach depends on the constraints, such as the number of arrays and elements per array. Understanding these methods helps in solving similar problems efficiently in real-world scenarios.
| Approach | Time Complexity | Space Complexity | Best Use Case |
|---|---|---|---|
| Brute-Force | O(KN log(KN)) | O(KN) | Small datasets, simple implementation |
| Min Heap | O(KN log K) | O(KN) + O(K) | Large K, efficient extraction needed |
| Divide and Conquer | O(KN log K) | O(KN) + O(log K) | Very large datasets, optimal performance |
The Min Heap Approach and Divide and Conquer Approach both achieve O(KN log K) time complexity, making them the most efficient methods compared to the brute-force approach.
The brute-force method involves copying all elements and sorting them, resulting in O(KN log(KN)) time complexity. This is inefficient for large values of K and N due to excessive sorting operations.
A min heap allows efficient extraction of the smallest element from multiple arrays, reducing unnecessary sorting. Each insertion and deletion operation takes O(log K) time, leading to an overall time complexity of O(KN log K).
The Divide and Conquer method is useful when merging very large datasets, as it efficiently merges pairs of arrays step by step, maintaining optimal performance with O(KN log K) complexity.
Yes! These methods are used in database indexing, log merging, data streaming, and search engines where efficient merging of sorted data is required.
If K and N are small, the brute-force method may be sufficient. However, for larger datasets, the Min Heap or Divide and Conquer Approach is recommended to optimize performance.
Source: NxtWave CCBP
Original URL: https://www.ccbp.in/blog/articles/merge-k-sorted-arrays
Contact: [email protected] | +919390111761 (WhatsApp only)