I know how Merge Sort works, but How Merge Sort Code Works?

manpreet Best Answer 3 years ago

You can read this on Wikipedia:

function merge_sort(list m)
// Base case. A list of zero or one elements is sorted, by definition.
if length(m) <= 1
    return m

// Recursive case. First, *divide* the list into equal-sized sublists.
var list left, right
var integer middle = length(m) / 2
for each x in m before middle
     add x to left
for each x in m after or equal middle
     add x to right

// Recursively sort both sublists
left = merge_sort(left)
right = merge_sort(right)

// Then merge the now-sorted sublists.
return merge(left, right)

On line 1 there's a list of numbers, let's say 9 6 3 7 5 1 8 2

They say that merge_sort divides the list on 2 and 2 again and again until each list has only 1 integer left, like this one:

9 6 3 7 5 1 8 2 -->
9 6 3 7 - 5 1 8 2 -->
9 6 - 3 7 - 5 1 - 8 2 -->
9 - 6 - 3 - 7 - 5 - 1 - 8 - 2

And then the numbers are put together like this:

6 9 - 3 7 - 1 5 - 2 8 -->
3 6 7 9 - 1 2 5 8 -->
1 2 3 5 6 7 8 9 -->

But I don't see where in the code the list of integers are divided on 2 again and again until each has only 1 integer left?

var list left, right
var integer middle = length(m) / 2
for each x in m before middle
     add x to left
for each x in m after or equal middle
     add x to right

As I understand, on the code above, the list of numbers is divided to two different lists: 9 6 3 7 and 5 1 8 2

What then happens on the code below?

left = merge_sort(left)
right = merge_sort(right)

Can someone explain me how the merge_sort code above exactly works step by step?