Recursive Merge Sort

BEGIN recursive merge sort(elements)
  IF length of elements > 1 THEN
    #---------------- 1. RECURSIVELY BREAK APART:
    SET halfway_point TO length of elements divided by 2
    SET left_half TO elements up to halfway_point
    SET right_half TO remaining elements past halfway_point
    CALL recursive merge sort(left_half) #--- NOTHING CAUGHT
    CALL recursive merge sort(right_half) #--- ON RETURN
    
    #---------------- 2. SORT AND MERGE HALF SEGMENTS INTO WHOLE:
    SET elements to empty list
    WHILE length of left_half > 0 AND length of right_half > 1
      IF first element in left_half < first element in right_half THEN
        APPEND first element in left_half TO elements 
        REMOVE first element in left_half
      ELSE
        APPEND first element in right_half TO elements 
        REMOVE first element in right_half
      END IF
    END WHILE
    
    FOR remaining_element in left_half
      APPEND remaining_element TO elements
    END FOR 

    FOR remaining_element in right_half
      APPEND remaining_element TO elements
    END FOR 
  END IF
END recursive merge sort

def mergeSort(a):
    if len(a) > 1: 
        #---------------- 1. RECURSIVELY BREAK APART:
        mid = len(a) // 2
        L = a[:mid] 
        R = a[mid:] 
        mergeSort(L) #--- NOTHING CAUGHT
        mergeSort(R) #--- ON RETURN
        
        #---------------- 2. SORT AND MERGE HALF SEGMENTS INTO WHOLE:
        a.clear()
        while len(L) > 0 and len(R) > 0: 
            if L[0] <= R[0]: 
                a.append(L[0]) 
                L.pop(0) 
            else: 
                a.append(R[0]) 
                R.pop(0)
    
        for i in L:
            a.append(i)
    
        for i in R:
            a.append(i)
    
    return a #---------------- ONLY CAUGHT ON FINAL RETURN:

print(mergeSort([12,999,123,-4,11,5,51]))

Run Code