Stay home. Save Lives
Merge Sort

Merge Sort

The straightforward approach to implementing merging is to design a method that merges two disjoint ordered arrays of Comparable objects into a third array. This strategy is easy to implement: create an output array of the requisite size and then choose successively the smallest remaining item from the two input arrays to be the next item added to the output array.

However, when we mergesort a large array, we are doing a huge number of merges, so the cost of creating a new array to hold the output every time that we do a merge is problematic. It would be much more desirable to have an in-place method so that we could sort the first half of the array in place, then sort the second half of the array in place, then do the merge of the two halves by moving the items around within the array, without using a significant amount of other extra space. It is worthwhile to pause momentarily to consider how you might do that. At first blush, this problem seems to be one that must be simple to solve, but solutions that are known are quite complicated, especially by comparison to alternatives that use extra space.

Still, the abstraction of an in-place merge is useful. Accordingly, we use the method signature merge(a, lo, mid, hi) to specify a merge method that puts the result of merging the subarrays a[lo..mid] with a[mid+1..hi] into a single ordered array, leaving the result in a[lo..hi]. The code on the next page implements this merge method in just a few lines by copying everything to an auxiliary array and then merging back to the original.

You may also Like

Bubble Sort

Bubble Sort

December 31, 2020
Quick Sort

Quick Sort

December 31, 2020
Shell Sort

Shell Sort

December 31, 2020

Leave a reply

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

About Me

I am a dad of two wonderful boys, Utku Efe and Omer Eren, and married with Elif. In addition, I am an academician and AI/ML scientist because I worked more than 15 years in universities, have M.S and Ph.D. thesis and more than 20 scientific papers/presentations and 100 citations. Now people call me as a Principal Developer in my last company :).
I am really hungry on learning new technologies and get more fun while developing new softwares.

Stay Connected

Recent Posts

Merge Sort


Bubble Sort


Quick Sort


Categories

×