in-place merge sort
Given two arrays, larger one has enough space in the end to hold
the smaller array. Both the arrays are sorted. Merge the smaller one into larger
one so that ending array is sorted.
eg:
1, 3,55,66,77,_,_,_
5,9,20
output:
1,3,5,9, 20,55 66 ,77
the smaller array. Both the arrays are sorted. Merge the smaller one into larger
one so that ending array is sorted.
eg:
1, 3,55,66,77,_,_,_
5,9,20
output:
1,3,5,9, 20,55 66 ,77
start comparing elements of both array from end.
ReplyDelete1)compare 77 with 20 and put larger one at the end of first array.
2)decrement index of array and continue in this way.
The hole moves gradually leftward, and shrinks whenever an item from the
second array is inserted. When the hole is reduced to 0, the process is
complete.