Merge Sort

Merge sort is a divide and conquer algorithm that was invented by John von Neumann in 1945. It works by dividing an array into two halves, sorting each half, and then merging the sorted halves back together. Here’s the basic outline of the algorithm:

1) If the input array has a length of 0 or 1, then it is already sorted, so return it.
2) Divide the input array into two halves.
3) Recursively sort the two halves.
4) Merge the two sorted halves back together.

To merge the two sorted halves back together, the algorithm uses two pointers, one for each half, and a temporary array. It compares the elements at the pointers, and copies the smaller of the two elements into the temporary array. It then advances the pointer for the half that contained the smaller element, and repeats the process until one of the halves is fully copied into the temporary array. It then copies the remaining elements from the other half into the temporary array. Finally, it copies the elements from the temporary array back into the original array.

Here’s some pseudocode that shows the algorithm in more detail:

function merge_sort(array):
    if length of array <= 1:
        return array
    left_half = first half of array
    right_half = second half of array
    left_half_sorted = merge_sort(left_half)
    right_half_sorted = merge_sort(right_half)
    return merge(left_half_sorted, right_half_sorted)

function merge(left, right):
    result = new empty array of length (length of left) + (length of right)
    left_index = 0
    right_index = 0
    for i in 0 to length of result - 1:
        if left_index >= length of left:
            result[i] = right[right_index]
            right_index += 1
        else if right_index >= length of right:
            result[i] = left[left_index]
            left_index += 1
        else if left[left_index] <= right[right_index]:
            result[i] = left[left_index]
            left_index += 1
        else:
            result[i] = right[right_index]
            right_index += 1
    return result