Merge Sort

# Time complexity is O(nlogn)

def merge_sort(sequence):
    
    if len(sequence) > 1: # run if the sequence is greater than 1

        left_array = sequence[:len(sequence)//2]
        right_array = sequence[len(sequence)//2:]

        # Recursively split the array
        merge_sort(left_array)  
        merge_sort(right_array)

        # Merge the array
        i = 0
        j = 0
        k = 0

        while i < len(left_array) and j < len(right_array):
            if left_array[i] < right_array[j]:
                sequence[k] = left_array[i]
                i += 1

            else :            
                sequence[k] = right_array[j]
                j += 1

            k += 1

        # If the lenght of the left array is greater than right array,
        # append the elements in left array to the sequence
        while i < len(left_array):
            sequence[k] = left_array[i]
            i += 1
            k += 1

        
        # If the lenght of the right array is greater than left array,
        # append the elements in right array to the sequence

        while j < len(right_array):
            sequence[k] = right_array[j]
            j += 1
            k += 1   
    
    return sequence

# Check if the function is working correct
array_test = [5,8,3,9,5,0,9,387,9486,9,4,56]

merge_sort(array_test)

[0, 3, 4, 5, 5, 8, 9, 9, 9, 56, 387, 9486]