CODEWITHSUNDEEP
algorithmsortingmergesort
woss
woss

Reputation: 83

Confusion about the combine step in Merge Sort Code

I have a question about how Merge Sort on an array works. I understand the 'divide' step, which divides an input array into 1-length element. However, when it comes to 'merge' part (combine step), I got confused. For example, given the input 3 5 1 8 2, the divide process will result in 5 elements: 3,5,1,8,2. I only understand that the merge function will combine them to 3 5, 1 8, 2, but how does it continue to combine 3 5 and 1 8 ? Are there recursions involved in the 'combine' part?

Upvotes: 6

Views: 3056

Answers (2)

mrk
mrk

Reputation: 3191

When the two recursive sort routines return, you can safely assume that they have sorted their parts. The merge step combines these two sorted sub arrays. If the input is 3 5 1 8 2, the first recursive call sorts the first half and yields 3 5, the second recursive call sorts the second half and yields 1 2 8.

The merge step, which you asked about, combines these two sorted halves into one by repeatedly choosing the minimum of the two first elements of the two sub arrays and adding it to the result, as in this animation:

enter image description here

Upvotes: 8

Jobs
Jobs

Reputation: 3377

This animation should help you.

http://en.wikipedia.org/wiki/File:Merge-sort-example-300px.gif

The process is like this:

3 5 1 8 2

3, 5, 1, 8, 2

3 5 , 1 2 8

1 2 3 5 8

  1. Start with the unsorted list I of n input items.
  2. Break I into two halves I1 and I2, having ceiling(n/2) and floor(n/2) items.
  3. Sort I1 recursively, yielding the sorted list S1.
  4. Sort I2 recursively, yielding the sorted list S2.
  5. Merge S1 and S2 into a sorted list S.

At each iteration, the item having smallest key from the two input lists is chosen, and appended to the output list. Since the two input lists are sorted, there are only two items to test, so each iteration takes constant time.

Upvotes: 1

Related Questions