Merging Two Sorted Arrays
💡 Concept Name
Merge Two Sorted Arrays — Efficiently combine two already-sorted arrays into a single sorted array using the two-pointer method.
📘 Quick Intro
Merging sorted arrays is a classic programming problem (and a favorite in interviews!). The aim: combine two lists without disturbing their order — and do it faster than by sorting the entire combined set again.
🧠 Analogy / Short Story
Picture two lines at a movie theater — each person in each line is already arranged from shortest to tallest. If you want to create one big line, still sorted by height, you simply pick the shortest from the front of either line again and again. No need to re-sort everyone!
🔧 Technical Explanation
- Use two pointers, each starting at the front of one array.
- Compare the pointed values; move the pointer that has the smaller value into the merged array.
- Repeat until one array is fully traversed, then append the rest from the other.
- Time complexity: O(n + m) where n and m are the lengths of the arrays. Efficient, stable, and reliable!
💻 Real Code Example
// Two-pointer merge of sorted arrays in C#
int[] arr1 = { 1, 3, 5, 7 };
int[] arr2 = { 2, 4, 6, 8 };
int[] merged = new int[arr1.Length + arr2.Length];
int i = 0, j = 0, k = 0;
while (i < arr1.Length && j < arr2.Length)
{
if (arr1[i] < arr2[j])
merged[k++] = arr1[i++];
else
merged[k++] = arr2[j++];
}
while (i < arr1.Length)
merged[k++] = arr1[i++];
while (j < arr2.Length)
merged[k++] = arr2[j++];
Console.WriteLine(string.Join(", ", merged));
// Output: 1, 2, 3, 4, 5, 6, 7, 8
❓ Interview Q&A
Q1: What is the time complexity to merge two sorted arrays?
A: O(n + m), where n and m are the lengths of the arrays.
Q2: Why not sort after combining?
A: Because direct merging is faster than sorting the combined array.
Q3: What algorithm uses this merge technique?
A: Merge Sort.
Q4: Is extra space needed?
A: Yes, for the merged array.
Q5: Can this be done in-place?
A: Sometimes, with space and logic trade-offs.
Q6: Is array merging stable?
A: Yes — equal values keep their order.
Q7: What if arrays are not sorted?
A: You must sort them before merging.
Q8: Can this method be extended for k arrays?
A: Yes, using a min-heap or repeated pairwise merging.
Q9: Where is merging used in real-world systems?
A: External sorting, database query results, file merging, etc.
Q10: What’s the best structure for merging k arrays?
A: A min-heap (priority queue).
📝 MCQs
Q1. What is the time complexity to merge two sorted arrays?
- O(n^2)
- O(n log n)
- O(n + m)
- O(1)
Q2. What technique is used for merging?
- Sorting
- Binary search
- Two-pointer method
- Stack-based merge
Q3. Is merge sort based on this?
- No
- Yes
- Only in Java
- Only in LINQ
Q4. Which space is needed to store merged array?
- n
- m
- n + m
- 1
Q5. What happens if input arrays are unsorted?
- Works fine
- Throws error
- Result may be incorrect
- Auto sorts them
Q6. Which structure can merge k sorted arrays efficiently?
- Queue
- Min-Heap
- Stack
- Set
Q7. Is the merge operation stable?
- No
- Yes
- Only for integers
- Only for strings
Q8. When should arrays be merged?
- For random sort
- When preserving order is required
- Only in trees
- Always for strings
Q9. Can merging be done in-place?
- Yes always
- No never
- Sometimes with trade-offs
- Only in Python
Q10. Is merging used in databases?
- No
- Yes
- Only in RAM
- Only for logs
💡 Bonus Insight
Pro tip: If you ever use this pattern in an interview, narrate your approach out loud. Interviewers love when you explain the logic — especially why merging is O(n + m) and not O(n log n). This not only shows you know how to code, but you also understand “why”!
📄 PDF Download
Need a handy summary for your notes? Download this topic as a PDF!