Merge Three Sorted Arrays

Let's understand what we're being asked to do. We have three sorted arrays like arr1 = [1, 4, 7], arr2 = [2, 5, 8], and arr3 = [3, 6, 9], and we need to merge them into a single sorted array [1, 2, 3, 4, 5, 6, 7, 8, 9].

Tracing through manually: we'd compare the first elements of each array (1, 2, 3), pick the smallest (1), then compare the next available elements (4, 2, 3), pick 2, and so on.

Important constraint: Each input array is already sorted in ascending order. We're not sorting random data - we're merging pre-sorted sequences!

Edge cases to consider: What if one array is empty? What if all arrays have the same elements? What if arrays have vastly different lengths? What if we had K arrays instead of just three?

The simplest approach is to concatenate all three arrays into one large array, then sort the combined array. This ignores the fact that the input arrays are already sorted. While easy to implement (just use a built-in sort function), this approach doesn't leverage the sorted property and performs unnecessary comparisons.

def merge_three_sorted_arrays(arr1, arr2, arr3):
    """
    Brute force approach: Concatenate all three arrays and sort.
    This ignores the fact that input arrays are already sorted.
    Time: O(n log n) where n is total elements
    Space: O(n) for the merged array
    """
    # Concatenate all three arrays into one
    merged = arr1 + arr2 + arr3
    
    # Sort the combined array (inefficient - doesn't use sorted property)
    merged.sort()
    
    # Return the sorted result
    return merged

At each step, the next smallest element in the final merged array must be the smallest of the current front elements from all three arrays.

If we always pick the minimum among the three candidates (one from each array), we maintain sorted order in the result.

Instead of comparing every element with every other element (which would be very slow), we only need to compare the current candidates from each array.

This is much more efficient because we're leveraging the fact that each array is already sorted - we don't need to look ahead in any array.

Imagine three people, each holding a sorted deck of cards face-up. You're building a single sorted pile.

At each step, you look at the top card from each person's deck (the three visible cards), pick the smallest one, and add it to your pile. Then that person reveals their next card.

You never need to look at cards deeper in anyone's deck - the top cards are always the smallest remaining in each deck. This is the key insight for merging sorted sequences efficiently.

The optimal approach uses a min-heap (priority queue) to efficiently track the smallest available element across all three arrays. Initialize the heap with the first element from each array (along with array index and element index). Repeatedly extract the minimum element from the heap, add it to the result, and insert the next element from that same array into the heap. This ensures we always pick the globally smallest available element in O(log k) time, where k is the number of arrays.

import heapq
def merge_three_sorted_arrays(arr1, arr2, arr3):
    """
    Merge three sorted arrays using a min-heap.
    Time: O(n log k) where n is total elements, k=3 arrays.
    Space: O(k) for heap + O(n) for result.
    """
    # Initialize result array and min-heap
    result = []
    min_heap = []
    
    # Add first element from each non-empty array to heap
    # Heap stores tuples: (value, array_index, element_index)
    if arr1:
        heapq.heappush(min_heap, (arr1[0], 0, 0))
    if arr2:
        heapq.heappush(min_heap, (arr2[0], 1, 0))
    if arr3:
        heapq.heappush(min_heap, (arr3[0], 2, 0))
    
    # Arrays reference for easy access
    arrays = [arr1, arr2, arr3]
    
    # Process heap until empty
    while min_heap:
        # Extract minimum element
        value, array_idx, elem_idx = heapq.heappop(min_heap)
        
        # Add to result
        result.append(value)
        
        # If current array has more elements, add next to heap
        next_idx = elem_idx + 1
        if next_idx < len(arrays[array_idx]):
            next_value = arrays[array_idx][next_idx]
            heapq.heappush(min_heap, (next_value, array_idx, next_idx))
    
    return result

• Min-heap for K-way merge: When merging K sorted arrays (K≥2), use a min-heap of size K to track the smallest unprocessed element from each array - this reduces the problem from comparing all elements to just extracting the minimum K times, making it scalable beyond just 2-3 arrays.
• Tuple storage pattern: Store (value, array_index, element_index) tuples in your heap to track both the element's value and its origin - this allows you to know which array to pull the next element from after each extraction without losing context.
• Time complexity advantage: The heap approach achieves O(N log K) where N is total elements and K is number of arrays, compared to O(N*K) for naive pairwise comparison - as K grows, the logarithmic factor becomes crucial for performance.
• Index boundary pitfall: Always check if element_index + 1 < len(array) before pushing the next element from an array into the heap - forgetting this check causes index-out-of-bounds errors when an array is exhausted, especially with arrays of different lengths.
• K-way merge generalization: This heap-based pattern extends to merging K sorted linked lists, finding the Kth smallest element in K sorted arrays, and external sorting of large datasets - recognize any problem involving "multiple sorted sequences" as a K-way merge candidate.
• Space-time tradeoff insight: The heap uses O(K) extra space regardless of total array size, making it memory-efficient for large datasets - this is why external merge sort uses this technique to merge file chunks that don't fit in memory.