Merge Sort

def merge(leftArray, rightArray):
    # create the sorted array
    sortedArray = []
    
    # loop while there are elements in leftArray and rightArray
    while len(leftArray) > 0 and len(rightArray) > 0:
        # check if leftArray first item is < rightArray first item
        if leftArray[0] < rightArray[0]:
            # add leftArray first item to sortedArray
            sortedArray.append(leftArray[0])
            # remove item from leftArray
            leftArray.pop(0)
        else:
            # add rightArray first item to sortedArray
            sortedArray.append(rightArray[0])
            # remove item from rightArray
            rightArray.pop(0)

    # return sortedArray + items left in leftArray + items left in rightArray
    return sortedArray + leftArray + rightArray


def merge_sort(array):
    # save array's length
    N = len(array)
    # save array's middle index
    mid = N // 2

    # base case - array's length is equal to 1
    if N == 1:
        return array

    # divides the array in 2
    leftArray = array[:mid]
    rightArray = array[mid:]

    # recursive step
    leftArray = mergeSort(leftArray)
    rightArray = mergeSort(rightArray)

    # helper function call
    return merge(leftArray, rightArray)

mergeSort(array of numbers)
  if length(array) = 1
    stop recursion and return array

  divide the array in 2
    leftArray = from 0 to middle index 
    rightArray = from middle index to length(array)
  
  apply recursion
    leftArray = mergeSort(leftArray)
    rightArray = mergeSort(rightArray)
  
  merge both sorted halves and return the result