• 2

Merging two sorted arrays with smaller auxiliary array
  • mergesort
  • array
  • sorting
  • sortedarray
  •   
    subscribe
  • Posted: 7 years ago
  • Updated: 6 years ago
  • Edit
  • answers (1)
  • views (11256)

Suppose you are given two sorted subarrays, [a[0], a[1], ..., a[n-1]] and [a[n], a[n+1], ..., a[2n]] . How will you merge the two subarrays so that [a[0], a[1], ..., a[2n-1], a[2n]] is sorted using an auxiliary array of size n (instead of 2n )?


Posted Answers

  • Posted: 7 years ago
  • 1 0
  • Edit


  • Copy the subarray [ a[0], a[1], ..., a[n-1] ] into the auxilliary array [ storage[0], storage[1],...., storage[n-1] ].
  • Set counter i=0 at the first element of the storage, storage[0] , j=0 at the first element of the second subarray, a[n] and k=0 at the first element of the first subarray, a[0] .
  • Compare storage[i] and a[j] .
  • If a[j] > storage[i] ; a[k] = a[j] , k ++, j ++.
  • Else, a[k] = storage[i] , k ++, i ++.
  • Repeat until all the elements in the storage and the subarray [ a[n], a[n+1], ..., a[2n-1] ] is placed in the array.


Example- Suppose the given sorted subarrays are [10, 32, 55] and [9, 17, 28]. The algorithm works as :
You need to Sign In to post your solution.