Timsort

Tim Sort

Mergesort gives good average and worst-case complexities, O(n log n), but is slower than Insertion sort for the best-case. Timesort is a hybrid between Mergesort and Insertion sort that takes advantages of both algorithms. Here is the idea behind Timsort.

• Start performing Mergesort on the input list.
• For each partition, check if the size of the partition is smaller or equal to 64.
• If it is, stop Mergesort and start performing Insertion sort.
• If it is not, keep performing Mergesort.

Task 1 - TimSort

• Create two classes LastnameTimSort1 and LastnameTimSort2 under sort.
• Extend the AbstractSort class.
• Define the sort method in LastnameTimSort1 implementing the Timesort algorithm using Insertion sort.
• Define the sort method in LastnameTimSort2 implementing the Timesort algorithm using Shell sort.
• Ensure your program runs correctly. I'll perform several unit tests to assess the correctness of your program.
• MergeSort, InsertionSort, ShellSort.

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 MergeSort, LastnameTimSort1, and LastnameTimSort2:
• 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 TimSort.
• 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.