Merge sort is a recursive algorithm for sorting lists.

## Algorithm

This algorithm uses two assumptions

• It is easier to sort two smaller sorted lists than one big list
• lists of one item are already considered sorted

The list is recursively split at a pivot point (by convention the middle node in the list). Once you hit a single item that item can be returned. When joining larger lists, repeatedly compare the two items at the start of each list and add the smaller item onto the result list until one of the lists runs out. Then the remaining list can be added onto the end of the result list.

## Pseudocode

```merge_sort(arr)
initialize list left, right
if arr.count ≤ 1
return arr

middle = arr.count / 2   // integer division
for each x in arr up to middle
for each x in arr after middle
left = merge_sort(left)
right = merge_sort(right)
result = merge(left, right)
return result

merge(left, right)
initialize list result
while left.count > 0 and right.count > 0
if left at 0 ≤ right at 0
left.remove at 0
else