Click here to Skip to main content
14,301,797 members
Rate this:
Please Sign up or sign in to vote.
See more:
I am trying to understand this code that I have found online however, I can't understand it because something is confusing me. As you can see below, I have put a asterisk on the confusing part. At *1 it is running the 'merge_sort' function recursively so how come at *2 it is able to return the function 'merge'.I would ofhave thought that the compiler couldn't run *2 because of the recursive call at list 1*.

please could someone explain to me how this works because I cannot progress further until I can find out how it works.

What I have tried:

def merge_sort(array):

    if len(array) <= 1:
        return array

    midpoint = int(len(array) / 2)

    *1 left, right = merge_sort(array[:midpoint]), merge_sort(array[midpoint:])

    *2 return merge(left, right)


def merge(left, right):
    
    result = []
    left_pointer = right_pointer = 0

    while left_pointer < len(left) and right_pointer < len(right):

        if left[left_pointer] < right[right_pointer]:

            result.append(left[left_pointer])
            left_pointer += 1

        else:

            result.append(right[right_pointer])
            right_pointer += 1

    result.extend(left[left_pointer:])
    result.extend(right[right_pointer:])

    return result
Posted
Updated 25-Jun-19 10:14am
v3
Rate this:
Please Sign up or sign in to vote.

Solution 1

Look at the first two lines of the merge_sort method:
if len(array) <= 1:
    return array

At some point the method will return and fall through to the final (*2) line of the method.

Add some (very small) test data, and a few print statements and you will be able to see exactly what it does.
   
Comments
CPallini 25-Jun-19 16:01pm
   
5.
Rate this:
Please Sign up or sign in to vote.

Solution 2

Quote:
I am trying to understand this code that I have found online however, I can't understand it because something is confusing me.

Have a look here: Merge sort - Wikipedia[^], there is a little animation.

Otherwise, you can the code perform with the help of a debugger :
Your code do not behave the way you expect, or you don't understand why !

There is an almost universal solution: Run your code on debugger step by step, inspect variables.
The debugger is here to show you what your code is doing and your task is to compare with what it should do.
There is no magic in the debugger, it don't know what your cpde is supposed to do, it don't find bugs, it just help you to by showing you what is going on. When the code don't do what is expected, you are close to a bug.
To see what your code is doing: Just set a breakpoint and see your code performing, the debugger allow you to execute lines 1 by 1 and to inspect variables as it execute.

Debugger - Wikipedia, the free encyclopedia[^]

Mastering Debugging in Visual Studio 2010 - A Beginner's Guide[^]
Basic Debugging with Visual Studio 2010 - YouTube[^]

27.3. pdb — The Python Debugger — Python 3.6.1 documentation[^]
Debugging in Python | Python Conquers The Universe[^]
pdb – Interactive Debugger - Python Module of the Week[^]

The debugger is here to only show you what your code is doing and your task is to compare with what it should do.
   
v2
Comments
CPallini 25-Jun-19 16:01pm
   
5.
Patrice T 25-Jun-19 16:34pm
   
Thank you for the intention, but are you sure you did it ? :)
CPallini 25-Jun-19 16:45pm
   
OOOPS :-O
Fixed now.
Patrice T 25-Jun-19 17:05pm
   
:) Thank you
Rate this:
Please Sign up or sign in to vote.

Solution 3

Richard already gave you the correct answer. Anyway, have a look at How Recursion Works — explained with flowcharts and a video[^].
   

This content, along with any associated source code and files, is licensed under The Code Project Open License (CPOL)




CodeProject, 503-250 Ferrand Drive Toronto Ontario, M3C 3G8 Canada +1 416-849-8900 x 100