Click here to Skip to main content
15,867,453 members
Please Sign up or sign in to vote.
0.00/5 (No votes)
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:

Python
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 14-Jan-20 5:55am
v3

Look at the first two lines of the merge_sort method:
Python
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.
 
Share this answer
 
Comments
CPallini 25-Jun-19 16:01pm    
5.
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.
 
Share this answer
 
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
Richard already gave you the correct answer. Anyway, have a look at How Recursion Works — explained with flowcharts and a video[^].
 
Share this answer
 

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



CodeProject, 20 Bay Street, 11th Floor Toronto, Ontario, Canada M5J 2N8 +1 (416) 849-8900