Mergesort

MergeSort(A, left, right)
{
  if (left < right)
  {
    mid = (left+right)/2
    MergeSort(A, left, mid)                 // recursively sort leftside of A
    MergeSort(A, mid+1, right)              // recursively sort rightside of A
    Merge(A, left, mid+1,  right)           // merge two sorted sides
  }
}

Example:
```
3 6 8 4 7 1 5 2
```
Analysis
What is the recurrence relation?
What is the worst case running time?

-> i