Merge sorted arrays
Given 2 arrays that contain numbers that are already in sorted order, merge them into a single sorted array in O(n) time. Assume there is enough space at the end of first array to accommodate the result array.
Example
i/p:
[3,4,6,10,11,15,nil,nil,nil,nil,nil,nil]
[1,5,8,12,14,19]
o/p:
[1,3,4,5,6,8,10,11,12,14,15,19]
Solution
- Hint: Since there is additional space towards the end of the array begin the comparison and merge from the end of the arrays
- Find the larger element from the tail of the arrays and proceed towards the start of the array
- Make sure you handle the case with disproportionte array sizes after the merge
Code
def sorted_merge(a1, a2)
return a2 if a1.nil?
return a1 if a2.nil?
# find last element in a1
i = a1.size
while a1[i].nil?
i -= 1
end
# last element in a2
j = a2.size - 1
# last element of sorted array
k = a1.size - 1
while i>=0 && j>=0
puts "a1[i]: #{a1[i]}, a2[j]: #{a2[j]}"
if a1[i] > a2[j]
a1[k] = a1[i]
i -= 1
else
a1[k] = a2[j]
j -= 1
end
k -= 1
end
# Elements left in a1
while i > 0
a1[k] = a 1[i]
i -= 1
k -= 1
end
# Elements left in a2
while j > 0
a1[k] = a2[j]
j -= 1
k -= 1
end
a1
end
Complexity
- O(n) since we are traversing over both arrays only once