merge sorted arrays

We have two sorted array. Without using additional memory we need to merge these two arrays(sec开发者_如何学Pythonond array is having more space for merging). Output should return through second array

Assuming the addtional space is at the end of the second array, simply start merging from the end of the arrays. Use two indices i1 and i2 pointing at the current positions in the arrays and an index i pointing to the current position in the merged array.

1. Initialise i, i1 and i2 to point to the last items of the respective arrays.

2. Iterate: Write the maximum of a1[i1] and a2[i2] to a2[i] and adjust the indices (i.e. decrease i and the index of the array holding the bigger value).