Given two sorted arrays A and B of size (m+n) and m respectively, design an algorithm to merge A and B in-place.
e.g. A = {8, 12, 15, 20, 22, 0, 0, 0, 0}
B = {6, 13, 18, 19}
Result= {6, 8, 12, 13, 15, 18, 19, 20, 22}
Approach
Apply 2-way merge. Advantage of this method is - it can be extended for any number of arrays (k-way merge). Take the last elements of arrays (22 and 19), put the highest element to the end of Array A. Next take 20 and the previous smaller element (19). Compare and put 20 in the last but one position. so on..
Solution
e.g. A = {8, 12, 15, 20, 22, 0, 0, 0, 0}
B = {6, 13, 18, 19}
Result= {6, 8, 12, 13, 15, 18, 19, 20, 22}
Approach
Apply 2-way merge. Advantage of this method is - it can be extended for any number of arrays (k-way merge). Take the last elements of arrays (22 and 19), put the highest element to the end of Array A. Next take 20 and the previous smaller element (19). Compare and put 20 in the last but one position. so on..
Solution
No comments:
Post a Comment