Loading learning content...
The merge operation is one of the most important primitives in computer science. It takes two (or more) already-sorted sequences and combines them into a single sorted sequence efficiently.
This operation is the heart of merge sort—one of the most important sorting algorithms, guaranteeing O(n log n) performance even in the worst case. But merging extends far beyond sorting:
By the end of this page, you will deeply understand the two-pointer merge technique, in-place merge variations, merging k sorted arrays efficiently, the merge step of merge sort, and real-world applications of merging in production systems.
Problem Statement:
Given two sorted arrays, combine them into a single sorted array.
Input: arr1 = [1, 3, 5, 7], arr2 = [2, 4, 6, 8]
Output: [1, 2, 3, 4, 5, 6, 7, 8]
The Two-Pointer Approach:
The key insight is that since both arrays are sorted, the smallest unprocessed element is always at one of the two front pointers. We compare, take the smaller, and advance that pointer.
123456789101112131415161718192021222324252627282930313233343536373839404142434445464748
/** * Merge two sorted arrays into a new sorted array. * * Time Complexity: O(n + m) — each element processed exactly once * Space Complexity: O(n + m) — new array for combined result * * @param arr1 First sorted array * @param arr2 Second sorted array * @returns New sorted array containing all elements from both */function mergeSortedArrays(arr1: number[], arr2: number[]): number[] { const result: number[] = []; let i = 0; // Pointer for arr1 let j = 0; // Pointer for arr2 // Compare elements from both arrays while (i < arr1.length && j < arr2.length) { if (arr1[i] <= arr2[j]) { result.push(arr1[i]); i++; } else { result.push(arr2[j]); j++; } } // Copy remaining elements from arr1 (if any) while (i < arr1.length) { result.push(arr1[i]); i++; } // Copy remaining elements from arr2 (if any) while (j < arr2.length) { result.push(arr2[j]); j++; } return result;} // Exampleconst mixed = mergeSortedArrays([1, 3, 5, 7], [2, 4, 6, 8]);console.log(mixed); // [1, 2, 3, 4, 5, 6, 7, 8] // Handles unequal lengthsconst unequal = mergeSortedArrays([1, 5, 9], [2, 3, 4, 6, 7, 8, 10]);console.log(unequal); // [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]Visualization:
arr1: [1, 3, 5, 7] arr2: [2, 4, 6, 8]
↑ ↑
i j
Step 1: 1 ≤ 2 → take 1, i++
Step 2: 3 > 2 → take 2, j++
Step 3: 3 ≤ 4 → take 3, i++
Step 4: 5 > 4 → take 4, j++
Step 5: 5 ≤ 6 → take 5, i++
Step 6: 7 > 6 → take 6, j++
Step 7: 7 ≤ 8 → take 7, i++
Step 8: arr1 exhausted → take remaining from arr2: 8
Result: [1, 2, 3, 4, 5, 6, 7, 8]
Using <= instead of < when comparing ensures stability: when elements are equal, we take from the first array first. This preserves relative order of equal elements, which is important in merge sort and when merging records with keys.
A classic interview problem: merge two sorted arrays where the first array has enough space to hold both.
Problem:
You are given two sorted arrays nums1 and nums2. Merge nums2 into nums1 in-place. nums1 has length m + n, with the first m elements to be merged and the last n elements initialized to 0 (placeholders).
Input: nums1 = [1,2,3,0,0,0], m = 3, nums2 = [2,5,6], n = 3
Output: [1,2,2,3,5,6]
The Key Insight: Start from the End
If we merge from the beginning, we'd overwrite elements in nums1 before processing them. Instead, we fill nums1 from the back, placing the largest elements first. This way, we never overwrite unprocessed elements.
12345678910111213141516171819202122232425262728293031323334353637383940
/** * Merge nums2 into nums1 in-place. * nums1 has enough space (length m+n) to hold all elements. * * Key insight: Start from the end to avoid overwriting. * * Time Complexity: O(m + n) * Space Complexity: O(1) — truly in-place */function merge(nums1: number[], m: number, nums2: number[], n: number): void { // Pointers for reading from the end of actual elements let p1 = m - 1; // Last actual element in nums1 let p2 = n - 1; // Last element in nums2 let p = m + n - 1; // Position to write in nums1 // Merge backwards while (p1 >= 0 && p2 >= 0) { if (nums1[p1] > nums2[p2]) { nums1[p] = nums1[p1]; p1--; } else { nums1[p] = nums2[p2]; p2--; } p--; } // Copy remaining elements from nums2 (if any) // Note: If p1 >= 0, those elements are already in place while (p2 >= 0) { nums1[p] = nums2[p2]; p2--; p--; }} // Exampleconst nums1 = [1, 2, 3, 0, 0, 0];merge(nums1, 3, [2, 5, 6], 3);console.log(nums1); // [1, 2, 2, 3, 5, 6]Why Start from the End?
Consider merging [1,2,3,0,0,0] with [2,5,6] starting from the front:
Step 1: Compare 1 and 2. Place 1 at position 0 ✓
Step 2: Compare 2 and 2. Place 2 at position 1 ✓
Step 3: Compare 3 and 2. Place 2 at position 2.
But wait — we just overwrote the 3 we needed!
Starting from the end:
Step 1: Compare 3 and 6. Place 6 at position 5. ✓
Step 2: Compare 3 and 5. Place 5 at position 4. ✓
Step 3: Compare 3 and 2. Place 3 at position 3. ✓
Step 4: Compare 2 and 2. Place 2 at position 2. ✓
Step 5: Compare 1 and remaining 2. Place 2 at position 1. ✓
Step 6: Place remaining 1 at position 0 (already there). ✓
No overwrites because we're always writing to positions we've already "passed" with our read pointers.
Notice we only handle remaining nums2 elements in the cleanup loop. If nums1 elements remain (p1 >= 0), they're already in their correct positions in nums1—no copying needed.
The merge technique applies directly to linked lists. In fact, it's often simpler because we can rewire pointers rather than copying elements.
Merge Two Sorted Lists:
1234567891011121314151617181920212223242526272829303132333435
interface ListNode { val: number; next: ListNode | null;} /** * Merge two sorted linked lists. * * Time Complexity: O(n + m) * Space Complexity: O(1) — only pointer manipulation */function mergeTwoLists( list1: ListNode | null, list2: ListNode | null): ListNode | null { // Dummy head simplifies edge cases const dummy: ListNode = { val: 0, next: null }; let tail = dummy; while (list1 !== null && list2 !== null) { if (list1.val <= list2.val) { tail.next = list1; list1 = list1.next; } else { tail.next = list2; list2 = list2.next; } tail = tail.next; } // Attach remaining nodes tail.next = list1 !== null ? list1 : list2; return dummy.next;}Using a dummy head node eliminates special-case logic for the first node. We build the list after the dummy, then return dummy.next. This pattern appears frequently in linked list problems.
Comparison: Array Merge vs. List Merge:
| Aspect | Array Merge | Linked List Merge |
|---|---|---|
| Space | O(n+m) new array typically | O(1) pointer rewiring |
| Cache Locality | Excellent | Poor |
| In-place Merge | Tricky (needs extra space) | Natural (pointer manipulation) |
| Random Access | Yes | No |
| Implementation | Index management | Pointer management |
The two-way merge extends to k-way merge: combining k sorted arrays into a single sorted result. This is essential for:
Naive Approach:
Merge arrays pairwise: merge arr[0] with arr[1], merge result with arr[2], etc.
Optimal Approach: Min-Heap
Use a min-heap to track the smallest current element from each array. Extract min, add to result, insert next element from that array.
123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101
/** * K-Way Merge using a Min-Heap * * Pseudocode (using a min-heap): * * 1. Insert first element of each array into heap, with array index * 2. While heap not empty: * - Extract minimum element * - Add to result * - Insert next element from same array (if exists) * * Time: O(n log k) — n total elements, each heap op is O(log k) * Space: O(k) — heap holds at most k elements at any time */ // Min-heap entry: [value, arrayIndex, elementIndex]type HeapEntry = [number, number, number]; function mergeKSortedArrays(arrays: number[][]): number[] { const result: number[] = []; // Simple min-heap implementation for illustration // In production, use a proper heap library const heap: HeapEntry[] = []; // Helper functions for heap operations const parent = (i: number) => Math.floor((i - 1) / 2); const leftChild = (i: number) => 2 * i + 1; const rightChild = (i: number) => 2 * i + 2; const swap = (i: number, j: number) => { [heap[i], heap[j]] = [heap[j], heap[i]]; }; const heapifyUp = (i: number) => { while (i > 0 && heap[parent(i)][0] > heap[i][0]) { swap(i, parent(i)); i = parent(i); } }; const heapifyDown = (i: number) => { let smallest = i; const left = leftChild(i); const right = rightChild(i); if (left < heap.length && heap[left][0] < heap[smallest][0]) { smallest = left; } if (right < heap.length && heap[right][0] < heap[smallest][0]) { smallest = right; } if (smallest !== i) { swap(i, smallest); heapifyDown(smallest); } }; const push = (entry: HeapEntry) => { heap.push(entry); heapifyUp(heap.length - 1); }; const pop = (): HeapEntry => { const min = heap[0]; heap[0] = heap[heap.length - 1]; heap.pop(); if (heap.length > 0) heapifyDown(0); return min; }; // Initialize heap with first element of each non-empty array for (let i = 0; i < arrays.length; i++) { if (arrays[i].length > 0) { push([arrays[i][0], i, 0]); } } // Extract minimum, add next element from same array while (heap.length > 0) { const [val, arrIdx, elemIdx] = pop(); result.push(val); // If more elements in this array, add next one if (elemIdx + 1 < arrays[arrIdx].length) { push([arrays[arrIdx][elemIdx + 1], arrIdx, elemIdx + 1]); } } return result;} // Exampleconst arrays = [ [1, 4, 7, 10], [2, 5, 8, 11], [3, 6, 9, 12]];console.log(mergeKSortedArrays(arrays));// [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12]| Approach | Time Complexity | Space | Notes |
|---|---|---|---|
| Sequential Pairwise | O(kn) | O(n) | Simple but inefficient |
| Divide & Conquer | O(n log k) | O(n + log k) | Merge pairs recursively |
| Min-Heap | O(n log k) | O(k) | Optimal, streaming-friendly |
K-way merge is crucial for external sorting. When data exceeds RAM, it's divided into chunks, each sorted in memory and written to disk. The merge phase combines these sorted runs using k-way merge, reading chunks incrementally to stay within memory limits.
Merge sort is a classic divide-and-conquer algorithm that uses the merge operation as its core step.
Algorithm Overview:
The merge operation is where the real work happens—it's O(n) per level, with O(log n) levels, giving O(n log n) total.
12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152
/** * Merge Sort implementation. * * Time Complexity: O(n log n) — guaranteed, no worst case degradation * Space Complexity: O(n) — auxiliary array for merging * * Properties: * - Stable (preserves order of equal elements) * - Not in-place (needs O(n) extra space) * - Predictable performance (always n log n) */function mergeSort(arr: number[]): number[] { // Base case if (arr.length <= 1) { return arr.slice(); // Return copy } // Divide const mid = Math.floor(arr.length / 2); const left = arr.slice(0, mid); const right = arr.slice(mid); // Conquer const sortedLeft = mergeSort(left); const sortedRight = mergeSort(right); // Combine return mergeSortedArrays(sortedLeft, sortedRight);} // Helper function (from earlier)function mergeSortedArrays(arr1: number[], arr2: number[]): number[] { const result: number[] = []; let i = 0, j = 0; while (i < arr1.length && j < arr2.length) { if (arr1[i] <= arr2[j]) { result.push(arr1[i++]); } else { result.push(arr2[j++]); } } while (i < arr1.length) result.push(arr1[i++]); while (j < arr2.length) result.push(arr2[j++]); return result;} // Exampleconsole.log(mergeSort([38, 27, 43, 3, 9, 82, 10]));// [3, 9, 10, 27, 38, 43, 82]Optimized In-Place Merge Sort:
The version above creates new arrays at each level. A more memory-efficient version uses a single auxiliary array and merges in-place:
1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253
/** * Optimized Merge Sort using single auxiliary array. * Avoids repeated array allocation. */function mergeSortOptimized(arr: number[]): void { const aux = new Array(arr.length); mergeSortHelper(arr, aux, 0, arr.length - 1);} function mergeSortHelper( arr: number[], aux: number[], lo: number, hi: number): void { if (lo >= hi) return; const mid = lo + Math.floor((hi - lo) / 2); mergeSortHelper(arr, aux, lo, mid); mergeSortHelper(arr, aux, mid + 1, hi); mergeInPlace(arr, aux, lo, mid, hi);} function mergeInPlace( arr: number[], aux: number[], lo: number, mid: number, hi: number): void { // Copy to auxiliary array for (let k = lo; k <= hi; k++) { aux[k] = arr[k]; } let i = lo; // Pointer for left half let j = mid + 1; // Pointer for right half // Merge back to arr[lo..hi] for (let k = lo; k <= hi; k++) { if (i > mid) { arr[k] = aux[j++]; // Left exhausted } else if (j > hi) { arr[k] = aux[i++]; // Right exhausted } else if (aux[j] < aux[i]) { arr[k] = aux[j++]; // Right is smaller } else { arr[k] = aux[i++]; // Left is smaller or equal (stable) } }}Unlike quicksort, merge sort guarantees O(n log n) performance—no pathological inputs can degrade it to O(n²). This makes merge sort preferred for external sorting, linked lists (where its overhead is lower), and when stability is required.
Counting inversions is a classic problem that merge sort solves elegantly. An inversion is a pair (i, j) where i < j but arr[i] > arr[j]—elements that are "out of order."
Applications:
Naive Approach: Check all pairs → O(n²)
Merge Sort Approach: Count inversions during merge → O(n log n)
Key Insight: When merging, if we take an element from the right half, all remaining elements in the left half form inversions with it.
12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061626364656667686970717273747576
/** * Count inversions in an array using modified merge sort. * * An inversion is a pair (i, j) where i < j and arr[i] > arr[j]. * * Time: O(n log n) * Space: O(n) */function countInversions(arr: number[]): number { const temp = new Array(arr.length); return mergeSortAndCount(arr, temp, 0, arr.length - 1);} function mergeSortAndCount( arr: number[], temp: number[], left: number, right: number): number { let invCount = 0; if (left < right) { const mid = Math.floor((left + right) / 2); // Count inversions in left half invCount += mergeSortAndCount(arr, temp, left, mid); // Count inversions in right half invCount += mergeSortAndCount(arr, temp, mid + 1, right); // Count split inversions during merge invCount += mergeAndCount(arr, temp, left, mid, right); } return invCount;} function mergeAndCount( arr: number[], temp: number[], left: number, mid: number, right: number): number { let i = left; // Left half pointer let j = mid + 1; // Right half pointer let k = left; // Merged array pointer let invCount = 0; while (i <= mid && j <= right) { if (arr[i] <= arr[j]) { temp[k++] = arr[i++]; } else { temp[k++] = arr[j++]; // All remaining elements in left half are greater than arr[j] // They form inversions with arr[j] invCount += (mid - i + 1); } } // Copy remaining elements while (i <= mid) temp[k++] = arr[i++]; while (j <= right) temp[k++] = arr[j++]; // Copy back to original array for (let x = left; x <= right; x++) { arr[x] = temp[x]; } return invCount;} // Exampleconst testArr = [8, 4, 2, 1];console.log(countInversions([...testArr])); // 6// Inversions: (8,4), (8,2), (8,1), (4,2), (4,1), (2,1)This example shows how the merge step can be augmented to solve related problems. The same technique applies to counting smaller elements after self, computing rank statistics, and more. The merge is doing work anyway—we can piggyback additional computations.
The merge technique naturally extends to computing intersection and union of sorted arrays—fundamental set operations.
Intersection: Elements present in both arrays Union: All unique elements from both arrays
1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162
/** * Find intersection of two sorted arrays. * Returns elements present in both. * * Time: O(m + n), Space: O(min(m, n)) for result */function intersectSorted(arr1: number[], arr2: number[]): number[] { const result: number[] = []; let i = 0, j = 0; while (i < arr1.length && j < arr2.length) { if (arr1[i] === arr2[j]) { // Found common element result.push(arr1[i]); i++; j++; } else if (arr1[i] < arr2[j]) { i++; } else { j++; } } return result;} /** * Find union of two sorted arrays (no duplicates). * Returns all unique elements from both. * * Time: O(m + n), Space: O(m + n) for result */function unionSorted(arr1: number[], arr2: number[]): number[] { const result: number[] = []; let i = 0, j = 0; while (i < arr1.length && j < arr2.length) { if (arr1[i] < arr2[j]) { result.push(arr1[i++]); } else if (arr1[i] > arr2[j]) { result.push(arr2[j++]); } else { // Equal: add once, advance both result.push(arr1[i]); i++; j++; } } // Add remaining elements while (i < arr1.length) result.push(arr1[i++]); while (j < arr2.length) result.push(arr2[j++]); return result;} // Examplesconsole.log(intersectSorted([1, 2, 4, 5, 6], [2, 3, 5, 7]));// [2, 5] console.log(unionSorted([1, 2, 4, 5, 6], [2, 3, 5, 7]));// [1, 2, 3, 4, 5, 6, 7]These operations are fundamental to database query processing. When computing joins or set operations on sorted indices, merge-based algorithms provide optimal O(m+n) performance without requiring hash tables.
A famous hard problem: find the median of two sorted arrays in O(log(m+n)) time—without actually merging them.
Why This Is Hard:
The Key Insight:
The median divides the combined array into two equal halves. We binary search for the correct partition point such that:
1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162
/** * Find median of two sorted arrays in O(log(min(m,n))) time. * * Idea: Binary search for correct partition point. * * We partition both arrays such that: * |left elements| = |right elements| (±1) * max(left) ≤ min(right) */function findMedianSortedArrays( nums1: number[], nums2: number[]): number { // Ensure nums1 is shorter for O(log(min(m,n))) if (nums1.length > nums2.length) { return findMedianSortedArrays(nums2, nums1); } const m = nums1.length; const n = nums2.length; let lo = 0; let hi = m; while (lo <= hi) { // Partition indices const partitionX = Math.floor((lo + hi) / 2); const partitionY = Math.floor((m + n + 1) / 2) - partitionX; // Edge elements (use -Infinity/Infinity for boundaries) const maxLeftX = partitionX === 0 ? -Infinity : nums1[partitionX - 1]; const minRightX = partitionX === m ? Infinity : nums1[partitionX]; const maxLeftY = partitionY === 0 ? -Infinity : nums2[partitionY - 1]; const minRightY = partitionY === n ? Infinity : nums2[partitionY]; // Check if partition is correct if (maxLeftX <= minRightY && maxLeftY <= minRightX) { // Found correct partition if ((m + n) % 2 === 0) { return ( Math.max(maxLeftX, maxLeftY) + Math.min(minRightX, minRightY) ) / 2; } else { return Math.max(maxLeftX, maxLeftY); } } else if (maxLeftX > minRightY) { // Too far right in nums1 hi = partitionX - 1; } else { // Too far left in nums1 lo = partitionX + 1; } } throw new Error("Input arrays are not sorted");} // Examplesconsole.log(findMedianSortedArrays([1, 3], [2])); // 2console.log(findMedianSortedArrays([1, 2], [3, 4])); // 2.5This is one of the most challenging standard interview problems. The binary search approach requires careful handling of edge cases and boundary conditions. Practice this specific problem multiple times until the partition logic becomes intuitive.
Merging sorted arrays is a fundamental operation that underpins many algorithms and systems. Let's consolidate the key insights:
What's Next:
With merging sorted arrays mastered, we complete our array pattern toolbox with the final page on in-place transformations—techniques for rearranging array elements without extra space, from partitioning to the Dutch National Flag algorithm.
Merge operations are now part of your permanent toolkit. Whenever you see sorted sequences that need combining, the two-pointer merge should be your first instinct. This pattern scales from simple arrays to distributed systems processing billions of records.