# merge sort Posted on July 12, 2013 algorithms

This is another divide and conquer sorting algorithm.

- worst case: O(n log n)

## steps

- dive the unsorted list into sublists, until each list contains a single item.
- repeatedly merge the sublists until there is a single list.

The sorting takes place during the merge step.

## example

In this example, the two lists are split in half. Then recursively, split in half repeatedly until the base case. The base case is when the sub list has 0 or 1 items in the list.

Once the base case is reached, the sublists are merged and sorted until there is a single sorted list. The <=> is the ruby comparison operator, which is similar to c# IComparable interface, or java’s Comparable interface.

```
class MergeSort
def sort(items)
return items if items.size <= 1
pivot = items.size/2
left, right = items[0...pivot], items[pivot...items.size]
merge(sort(left), sort(right))
end
private
def merge(left, right)
result = []
result << ((left.first <=> right.first) == -1 ? left.shift : right.shift) until left.empty? || right.empty?
result + left + right
end
end
```