0

We have two sorted array. Without using additional memory we need to merge these two arrays(second array is having more space for merging). Output should return through second array

kc3
  • 4,281
  • 7
  • 20
  • 16
  • I have gone through Mergesort from back to front and final data will be generated at the end of the second array.This case second array or resultant array may have some empty spaces in the front. Any better way than this? – kc3 May 04 '11 at 15:28
  • 2
    just add up the sizes of the occupied areas of the arrays, and start from that position in the array instead of the very end. For example, assume A1 contains 10 elements and A2 8 elements, but A2 has room for 23 elements. Instead of starting from element 23 and working backward, start from element 18 and work backward. – Jerry Coffin May 04 '11 at 15:53
  • This link http://stackoverflow.com/questions/5958169/how-to-merge-two-sorted-arrays-into-a-sorted-array should solve your problem. – Exception Sep 09 '13 at 04:50

1 Answers1

7

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).

Sven Marnach
  • 574,206
  • 118
  • 941
  • 841