IntroSort

Introspective sort

Quicksort runs fast in general but it still cannot avoid the O(n^2) complexity for the worst case. On the other hand, Heapsort runs slightly slower than Quicksort in general but is guaranteed to run in O(n log n) for all cases. Introspective sort (Introsort) is a hybrid between Quicksort and Heapsort that takes advantages of both algorithms. Here is the idea behind Introsort.

• Start performing Quicksort on the input list.
• For each partition, check if its depth is greater than "2 · floor(log₂n)".
• If it is, stop Quicksort and start performing Heapsort.
• If it is not, keep performing Quicksort.

Task 1 - IntroSort

• Create a class IntroSort under sort.
• Extend the AbstractSort class.
• Define the sort method implementing the Introsort algorithm.
• Ensure your program runs correctly. I'll perform several unit tests to assess the correctness of your program.
• QuickSort, HeapSort.

Task 2 - Speed Comparison

• Create lists of 100, 200, ..., 1000 random comparable keys, keys in ascending order, and keys in descending order (you will end up creating 10*3 = 30 lists).
• For HeapSort, QuickSort, and IntroSort:
• Measure the time it takes to sort all keys in each list.
• Repeat this procedure 1K times, and sum the times for each algorithm.
• SortTest#compareSpeeds().

Task 3 - Report

• Explain briefly about your implementation of IntroSort.
• Create tables and charts showing the speed comparisons with respect to the nature of the lists and their sizes.
• Write analysis of the speed comparisons given different conditions.

Extra Credit

• Use Shellsort instead of Heapsort and compare its performance against other algorithms. Include the analysis using Shellsort in your report.
• ShellSort.