Sorting N/Slide 2 Lower Bound for Sorting Mergesort and heapsort worst-case running time is o(N log N) Are there better algorithms? Goal: Prove that any sorting algorithm based on only comparisons takes 2(N log n) comparisons in the worst case(worse-case input) to sort n elementsSorting IV / Slide 2 Lower Bound for Sorting Mergesort and heapsort worst-case running time is O(N log N) Are there better algorithms? Goal: Prove that any sorting algorithm based on only comparisons takes (N log N) comparisons in the worst case (worse-case input) to sort N elements