mergesort

"""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

// Merges two subarrays of arr[].
// First subarray is arr[l..m]
// Second subarray is arr[m+1..r]
function merge(arr, l, m, r)
{
    var n1 = m - l + 1;
    var n2 = r - m;
  
    // Create temp arrays
    var L = new Array(n1); 
    var R = new Array(n2);
  
    // Copy data to temp arrays L[] and R[]
    for (var i = 0; i < n1; i++)
        L[i] = arr[l + i];
    for (var j = 0; j < n2; j++)
        R[j] = arr[m + 1 + j];
  
    // Merge the temp arrays back into arr[l..r]
  
    // Initial index of first subarray
    var i = 0;
    // Initial index of second subarray
    var j = 0;
    // Initial index of merged subarray
    var k = l;
  
    while (i < n1 && j < n2) {
        if (L[i] <= R[j]) {
            arr[k] = L[i];
            i++;
        }
        else {
            arr[k] = R[j];
            j++;
        }
        k++;
    }
  
    // Copy the remaining elements of
    // L[], if there are any
    while (i < n1) {
        arr[k] = L[i];
        i++;
        k++;
    }
  
    // Copy the remaining elements of
    // R[], if there are any
    while (j < n2) {
        arr[k] = R[j];
        j++;
        k++;
    }
}
  
// l for left index r is
// right index of the sub-array
// of arr to be sorted
function mergeSort(arr,l, r){
    if(l>=r){
        return;//returns recursively
    }
    var m =l+ parseInt((r-l)/2);
    mergeSort(arr,l,m);
    mergeSort(arr,m+1,r);
    merge(arr,l,m,r);
}

function merge(left, right) {
    let arr = []
    // Break out of loop if any one of the array gets empty
    while (left.length && right.length) {
        // Pick the smaller among the smallest element of left and right sub arrays 
        if (left[0] < right[0]) {
            arr.push(left.shift())  
        } else {
            arr.push(right.shift()) 
        }
    }
    
    // Concatenating the leftover elements
    // (in case we didn't go through the entire left or right array)
    return [ ...arr, ...left, ...right ]
}