Merge sort

An initial array is divided into two roughly equal parts. If the array has an odd number of elements, one of those “halves” is by one element larger than the other.

The subarrays are divided over and over again into halves until you end up with arrays that have only one element each.

Then you combine the pairs of one-element arrays into two-element arrays, sorting them in the process. Then these sorted pairs are merged into four-element arrays, and so on until you end up with the initial array sorted.

Interview question

You are given two sorted arrays, A and B, and A has a large enough buffer at the end to hold B. Write a method to merge B into A in sorted order.

Leave a Reply

Your email address will not be published. Required fields are marked *