Merge Two Sorted Lists (Array Representation)
Maintained by Vikas D, software engineer
You receive two input arrays, list1 and list2. Each one is already arranged so that values never decrease as you move from left to right, and either array may be empty.
Your job is to produce a single new array that holds every value from both inputs while preserving the same non-decreasing order. Duplicate values are allowed and must all appear in the result.
This is the array version of merging two sorted linked lists. Because both inputs are pre-sorted, you do not need a full sort. Walking the two arrays together and always taking the smaller front value is enough to build the answer in one pass.
Examples
Compare fronts and take the smaller each time. The two 1s come first, then 2 from list1, then 3 from list2, then both 4s. Equal values keep their relative order.
Both inputs are empty, so there is nothing to merge and the result is an empty array.
The smallest front alternates between the two arrays, so the merged output interleaves them into one sorted sequence.
Constraints
- 0 <= list1.length, list2.length <= 50
- -100 <= list1[i], list2[i] <= 100
- Both list1 and list2 are sorted in non-decreasing order.
- Either array (or both) may be empty.
- Duplicate values can appear within and across the two arrays.
Visible test cases
- mergeTwoLists([1,2,4], [1,3,4]) == [1,1,2,3,4,4]
- mergeTwoLists([], []) == []
- mergeTwoLists([], [0]) == [0]
- mergeTwoLists([1,3,5], [2,4,6]) == [1,2,3,4,5,6]
- mergeTwoLists([1,2,3], [4,5,6]) == [1,2,3,4,5,6]
- mergeTwoLists([-3,-1,0], [-2,1,2]) == [-3,-2,-1,0,1,2]
Hints
Hint 1
You do not need to sort from scratch. Both arrays are already sorted, so think about how to merge rather than how to order.
Hint 2
Keep one index into each array. At every step compare the two current front values and copy the smaller one into the result, then advance only that index.
Hint 3
When one array runs out, the other array's remaining tail is already sorted, so append the rest of it directly without any more comparisons.
Approaches
Concatenate then sort
Time O((m + n) log(m + n)) · Space O(m + n)Ignore that the inputs are sorted, join them into one array, and let a general sort fix the order.
- Build a combined array containing every element of list1 followed by every element of list2.
- Sort the combined array in non-decreasing order.
- Return the sorted array.
Two-pointer merge
Time O(m + n) · Space O(m + n)Because both inputs are already sorted, repeatedly take the smaller of the two front elements to build the result in a single pass.
- Create an empty result array and two indices i and j starting at 0.
- While both indices are still in range, compare list1[i] with list2[j]; push the smaller (or list1[i] when they are equal) and advance that index.
- When one array is exhausted, append every remaining element of the other array in order.
- Return the result array.
Common mistakes
- Forgetting to copy the leftover tail of whichever array still has elements after the main loop ends, which silently drops values.
- Using a strict less-than comparison without a clear tie rule and reordering equal values; pushing list1[i] when values are equal keeps a stable, predictable order.
- Assuming at least one array is non-empty; both can be empty and the answer is then an empty array.
- Mishandling negative numbers by comparing absolute values instead of the signed values.
Follow-up variations
- Solve it on real singly linked list nodes instead of arrays and splice the existing nodes together without allocating a new list.
- Merge k sorted arrays at once instead of just two, and discuss using a min-heap to keep it efficient.
- Merge in place when list1 has enough trailing space to hold both, writing from the back to avoid overwriting unread values.
- Return only the unique merged values, removing duplicates that span both inputs.