How fast can we sort? All the sorting algorithms we have seen so far are comparison sorts: only use comparisons to determine the relative order of elements E. g. insertion sort, merge sort, quicksort heapsort The best worst-case running time that we've seen for comparison sorting is o(nIgn) Is O(nlgn the best we can do? Decision trees can help us answer this question o 2001 by Charles E Leiserson Introduction to Algorithms Day 8 L5.2© 2001 by Charles E. Leiserson Introduction to Algorithms Day 8 L5.2 How fast can we sort? All the sorting algorithms we have seen so far are comparison sorts: only use comparisons to determine the relative order of elements. • E.g., insertion sort, merge sort, quicksort, heapsort. The best worst-case running time that we’ve seen for comparison sorting is O(n lg n). Is O(n lg n) the best we can do? Decision trees can help us answer this question