MergeSort

Worst case performance	 O(n log n)
Best case performance    O(n log n) typical, O(n) natural variant
Average case performance O(n log n)