### Merging two sorted arrays with smaller auxiliary array mergesort array sorting sortedarray    Posted: 5 years ago Edit answers (1) views (8646)

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

## Posted Answers

 Posted: 5 years ago Updated: 5 years ago 1 0 Edit Copy the subarray [ a, a, ..., a[n-1] ] into the auxilliary array [ storage, storage,...., storage[n-1] ]. Set counter i=0 at the first element of the storage, storage , j=0 at the first element of the second subarray, a[n] and k=0 at the first element of the first subarray, a . 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.