0

I wrote a short Merge sort algorithm in Python 3. I have trouble understanding how it manages to achieve the correct result, as when I try to trace its logical steps I end up with an out of order list. The annotated code can be seen below.

What I'm specifically referring to is the merging part of the code. The three 'while' loops.

Let me use an example to demonstrate what confuses me. I explain the details in the annotations.

Thank you in advance for your time and help.

Let's assume we want to merge two arrays.

left = [2,6]
right = [4,8]

def merge_sort(array):

    if len(array) > 1:

        middle = len(array)//2

        left = array[:middle]
        right = array[middle:]

        merge_sort(left)
        merge_sort(right)

        i = j = k = 0

        while i < len(left) and j < len(right):

            # i.e. if 2 < 4
            if left[i] < right[j]: 

                # The first index of the array is assigned the value 2
                array[k] = left[i]  

                # i = 1 now
                i += 1

            # The 'else' statement is not executed, because the 'if' statement was.
            else:

                array[k] = right[j]
                j += 1

            # k = 1 now
            k += 1 

        # The 'while' loop below assigns '6' as the value for index 1 of the array and terminates.
        # k = 2 now
        while i < len(left):
       
            array[k] = left[i]
            i += 1
            k += 1

        # The last 'while' loop assigns '4' and '8' to indexes 2 and 3 of the array, respectively.
        while j < len(right):

            array[k] = right[j]
            j += 1
            k += 1

        # The algorithm terminates and from what I can see I should end up with the array of [2,6,4,8].
        # I do not, however. It is sorted in ascending order and I cannot see where I'm making a mistake.
gallen
  • 1,252
  • 1
  • 18
  • 25
DeadManProp
  • 79
  • 7
  • How does this merge two lists when you only pass in one? Your example does not line up with the way the code is written. – gallen Jun 30 '20 at 21:17

2 Answers2

2

Firstly, careful with your wording, to be clear merge sort isn't merging distinct arrays, merge sort cleverly deconstructs a single unsorted array into sub-arrarys (in our case left and right) and sorts them individually and merges them back into a single array again with a final sort. In other words, you pass this function a single array unsorted and it returns a single sorted array. If you need to merge two arrays, you would do so before calling it.

Merge Sort

"Merge sort is a recursive algorithm that continually splits a list in half. If the list is empty or has one item, it is sorted by definition (the base case). If the list has more than one item, we split the list and recursively invoke a merge sort on both halves. Once the two halves are sorted, the fundamental operation, called a merge, is performed. Merging is the process of taking two smaller sorted lists and combining them together into a single, sorted, new list."

Debug/Analyze Code

To help with understanding how it works (and debug), inject print comments at the very least to best show what is going on in more detail. I have taken what you wrote and added print comments and pass the function a string to help determine which array (left or right) it is sorting. You can see the splitting sorting, and merging as it accomplishes the sort by splitting the array down to size one and merging the sorted sub arrays etc. in the process ...

def merge_sort(array,type):
    print('merge_sort =>' + type)
    if len(array) < 2:
        print('Array < 2 nothing changed')
        return array
    middle = len(array) // 2
    left = array[:middle]
    right = array[middle:]
    print('splitting : ' + str(array))
    merge_sort(left,'left')
    merge_sort(right,'right')
    i = j = k = 0
    print('sorting.. Left/Right:' + str(left) + str(right))
    while i < len(left) and j < len(right):
        if left[i] < right[j]:
            print(' - left[i] < right[j] ('+ str(left[i]) + ' < ' + str(right[j]) + ') set array[' + str(k) + '] = ' + str(left[i]) + '')
            array[k] = left[i]
            i += 1
        else:
            print(' - else left[i] >= right[j] ('+ str(left[i]) + ' >= ' + str(right[j]) + ') set array[' + str(k) + '] = ' + str(right[j]) + '')
            array[k] = right[j]
            j += 1
        k += 1
    while i < len(left):
        print(' - WHILE i < len(left), ('+str(i) +' < '+str(len(left))+'), set array[' + str(k) + '] = ' + str(left[i]) + '')
        array[k] = left[i]
        i += 1
        k += 1
    while j < len(right):
        print(' - while j < len(right) ('+str(j) +' < ' + str(len(right)) + '), set array[' + str(k) + '] = ' + str(right[j]) + '')
        array[k] = right[j]
        j += 1
        k += 1
    print("returning.." + str(array))
    return array

arr = [2,6,4,8]
result = merge_sort(arr,'full')
print(result)

Which provides the following output:

merge_sort =>full
splitting : [2, 6, 4, 8]
merge_sort =>left
splitting : [2, 6]
merge_sort =>left
Array < 2 nothing changed
merge_sort =>right
Array < 2 nothing changed
sorting.. Left/Right:[2][6]
 - left[i] < right[j] (2 < 6) set array[0] = 2
 - while j < len(right) (0 < 1), set array[1] = 6
returning..[2, 6]
merge_sort =>right
splitting : [4, 8]
merge_sort =>left
Array < 2 nothing changed
merge_sort =>right
Array < 2 nothing changed
sorting.. Left/Right:[4][8]
 - left[i] < right[j] (4 < 8) set array[0] = 4
 - while j < len(right) (0 < 1), set array[1] = 8
returning..[4, 8]
sorting.. Left/Right:[2, 6][4, 8]
 - left[i] < right[j] (2 < 4) set array[0] = 2
 - else left[i] >= right[j] (6 >= 4) set array[1] = 4
 - left[i] < right[j] (6 < 8) set array[2] = 6
 - while j < len(right) (1 < 2), set array[3] = 8
returning..[2, 4, 6, 8]

This yields something apx. like so: enter image description here

References: How do I merge arrays in python? https://runestone.academy/runestone/books/published/pythonds/SortSearch/TheMergeSort.html

Mike Q
  • 6,716
  • 5
  • 55
  • 62
  • 1
    Thank you for this exhaustive explanation and the time you've put into it! I do have a better idea of what is happening there now :) – DeadManProp Jul 01 '20 at 19:00
  • @DeadManProp thanks but I feel like I had the best answer lol (I was wrong lol) – Mike Q Jul 01 '20 at 19:11
  • Sorry, I didn't mean to make you feel underappreciated. I've marked that other response with a checkmark because it pointed out the exact "moment" in the execution of the code where I was making an error in tracing the steps. Nonetheless, your answer has allowed me to understand my code even better and if it were possible I would've given two checkmarks for sure. Sadly the system doesn't allow me to do so. – DeadManProp Jul 01 '20 at 19:41
1

It seems in your annotations you exit the first while loop prematurely, you stop after one run when the code actually does 3 runs. Here is how you would follow wgat actually happens:

  • you run through it once, then you have k=1, i=1 and j=0,
  • so you go through this loop again (this time it is the else that is executed, and assigns 4 to index 1 of the array, now k=2, i=1 and j=1
  • so you run through the loop a third time, with thte if executed, finally k=3, i=2 and j=1, so you get out of the first while.
Ariane
  • 326
  • 2
  • 11
  • Thank you so much! This is exactly what I was missing. It seems so clear now that I think about it, but somehow I was forgetting that the first 'while' loop should continue when i = 1. – DeadManProp Jul 01 '20 at 18:58