CODEWITHSUNDEEP
algorithmmergesort
Hazim
Hazim

Reputation: 381

Differences in variations of MergeSort?

I am taking a college course on Data Structures & Algorithms and am having some trouble with MergeSort. I have tried to look online but the results seem to be inconsistent.

When it comes to a normal MergeSort and a top down MergeSort - what are the differences? What I have read so far has led me to believe:

A "normal" MergeSort simply splits an already sorted array/file into half and puts this in an auxilary array. Then we begin to examine the auxilary array by consecutively comparing elements from the left with elements on the right, writing these elements into sorted order, back into the original array.

A top-down MergeSort recursively splits an unsorted array into smaller parts until we get an array of size 1 (techinically sorted), until which both original halves are sorted, and then a "normal" MergeSort is applied to get the final array.

I'm positive that my understanding is wrong - I'm having lots of trouble with MergeSort. Could someone clarify this for me?

Thanks.

Upvotes: 2

Views: 1795

Answers (2)

MBo
MBo

Reputation: 80187

The most popular variation of MergeSort is is top-down as Nick Zuber described in details.

Bottom-up variant doesn't divide whole array to smaller and smaller parts. Instead it
at the first stage merges arrays of length 1
at the second stage merges arrays of length 2
at the third stage merges arrays of length 4
ans so on until full length is reached.

Consider lines of Nick's scheme from the fourth line to the end - they are stages of bottom-up sort.

Upvotes: 1

Nick Zuber
Nick Zuber

Reputation: 5637

The whole idea of merge sort is to sort a list using a divide and conquer approach.

The rule is you can compare the elements of the right auxiliary array to the left auxiliary array only if both of them are sorted. When the list is initially unsorted, the only way we can guarantee that our subarray is sorted is when it's only 1 element. At this point we begin the merge portion which compares elements from the left and right auxiliary arrays and sorts them back into the main array.

Here's an example of what's going on when we merge sort:

https://en.wikipedia.org/wiki/Merge_sort

As you can see, we just half the array down until we get a guaranteed sorted array (just 1 element) and now we can being merging subarrays arrays together since they're sorted.

Here are some good sources if you want to read more about it, but it seems to me like you conceptually have a grasp on what merge sort is supposed to do, you just might have some of the techniques mixed up a bit.

Upvotes: 1

Related Questions