CODE EXAMPLE FOR PYTHON

merge sort python

"""Mergesort
	The cleaner version than geeks4geeks. Although check that code out too!
"""
## Method 1: Two functions
def mergesort(lst):
    # Is sortable
    if len(lst) > 1:
        # Get mid-point
        mid = len(lst) // 2
        
        # Recursive Partition
        left = mergesort(lst[:mid])
        right = mergesort(lst[mid:])
        
        # Merging
        return merge(left, right)
    return lst

def merge(left, right):
    new = []
    
    # Left and right not empty
    while left and right:
        # Compare 1st elements of left and right, sort accordingly
        if left[0] < right[0]:
            new.append(left.pop(0))
        else:
            new.append(right.pop(0))
    
    # Append the leftover nums
    return new + left + right

## Method 2: Nested functions
def merge(nums):
    # Recursive partition
    if len(nums) > 1:
        # Midpoint
        mid = len(nums) // 2
        
        left = merge(nums[:mid])
        right = merge(nums[mid:])
        
        # Sorting
        def go(left, right):
            newlist = []
            
            # Sort by comparing 1st elements of both lists
            while left and right:
                if left[0] < right[0]:
                    newlist.append(left.pop(0))
                else:
                    newlist.append(right.pop(0))
                    
            # Cleanup unsorted elements            
            return newlist + left + right
        return go(left, right)
    return nums