Choose the Fastest Sort Part I

Mergesort takes $O(n \lg n)$ time no matter the input. Bubble Sort takes $O(n^2)$ time when the input is not already sorted. Insertion Sort takes $O(n^2)$ when the input is relatively unordered since its average and worst case is $O(n^2)$ . The best case for Insertion Sort is $O(n)$ , but in order to achieve this running time, the input must already be fairly ordered. This input list is not sorted or close to sorted, so Mergesort is the fastest algorithm to sort this input.