CS 240: Algorithms and Data Structures
James Madison University, Fall 2024

Introduction - What is the World's Best Sorting Algorithm?

There is no single best sorting algorithm. Quicksort is the fastest known comparison-based sorting algorithm when applied to large, unordered, sequences. It also has the advantage of being an in-place (or nearly in-place) sort. Unfortunately, quicksort has some weaknesses: it's worst-case performance is \(O(n^2)\), and it is not stable. Merge sort shares neither of these disadvantages: it is stable and it requires \(O(n \log n)\) steps in the worst case. Unfortunately, merge sort requires \(O(n)\) additional space and it runs more slowly than quick sort on most inputs.

What we really want is a sorting algorithm that is as fast as quicksort, stable, in-place, with \(O(n \log n)\) worst-case performance. Sadly, no such algorithm has yet been discovered. In practice, most code libraries follow one of two paths: either they provide a modified version of quicksort that is able to avoid worst-case behavior on typical inputs, or they provide a modified version of merge sort that is able to close some of the performance gap through careful optimizations*.

The objective of this lab is to write modified version of mergesort that exhibits better performance than the standard version described in our textbook. You will implement two improvements that should improve the algorithm's performance without requiring a great deal of additional code. You will also experimentally evaluate the impact of your improvements.

The following zip file contains starter code, including the sort implementations provided by our textbook.

src.zip

This zip file has the following contents:

Note that SortProfiler relies on the JOpt Simple library for handling command-line arguments. You will need to have jopt-simple-5.0.4.jar in your classpath to use the application.

Part 1 - Evaluating Existing Sorts

SortProfiler.java is a command-line tool for running experimental timings on the provided sorting algorithms. Complete the following steps:

Part 2 - Improved Merges

The merge algorithm described in our textbook consists of the following two stages:

1. Copy all values from the two merge-sorted halves into a temporary array.
2. Merge the values from the temporary array back into the original array.

If \(n\) is the combined size of the two sub-arrays being merged, this algorithm requires a temporary array of size \(n\), and requires \(n\) assignment operations in stage 1. The following alternative approach cuts both of those values from \(n\) to around \(n/2\):

1. Copy the values from the first merge-sorted half to a temporary array.
2. Merge the values from the temporary array and the second
   merge-sorted half into the original array.

Here are some ASCII graphics illustrating the process:

Original sorted sub-arrays:

      ________________________________________
  ...| 1 | 3 | 5 | 7 | 9 | 2 | 4 | 6 | 8 | 10 |...
      ----------------------------------------
 start-^           mid-^               end-^

Temporary Array

      ___________________
     |   |   |   |   |   |...
      -------------------
     0-^

      ________________________________________
  ...| 1 | 3 | 5 | 7 | 9 | 2 | 4 | 6 | 8 | 10 |...
      ----------------------------------------
 start-^           mid-^               end-^

Copy the sorted first half into the temporary array:

         ___________________
        | 1 | 3 | 5 | 7 | 9 |...
         -------------------

         ________________________________________
     ...|   |   |   |   |   | 2 | 4 | 6 | 8 | 10 |...
         ----------------------------------------

Initialize i1 to be the index of the first position (0) in the temporary array, i2 to be the index of the first position of the sorted right half, and curr to be the next available position for merging:

         ___________________
        | 1 | 3 | 5 | 7 | 9 |...
         -------------------
       i1-^
         ________________________________________
     ...|   |   |   |   |   | 2 | 4 | 6 | 8 | 10 |...
         ----------------------------------------
     curr-^                i2-^

Since temp[i1] < items[i2], temp[i1] is copied to items[curr]. i1 and curr are incremented.

       ___________________
      | 1 | 3 | 5 | 7 | 9 |...
       -------------------
         i1-^
       ________________________________________
   ...| 1 |   |   |   |   | 2 | 4 | 6 | 8 | 10 |...
       ----------------------------------------
       curr-^            i2-^

Since items[i2] < temp[i1], items[i2] is copied to items[curr]. i2 and curr are incremented.

       ___________________
      | 1 | 3 | 5 | 7 | 9 |...
       -------------------
         i1-^
       ________________________________________
   ...| 1 | 2 |   |   |   | 2 | 4 | 6 | 8 | 10 |...
       ----------------------------------------
           curr-^            i2-^

Continue Merging until complete:

       ___________________
      | 1 | 3 | 5 | 7 | 9 |...
       -------------------
       ________________________________________
   ...| 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 |...
       ----------------------------------------

Test your finished implementation of mergeSort1 using the provided unit tests.

Part 3 - Switching Strategies

The next improvement is based on the observation that merge sort is actually slower than simple \(\Theta(n^2)\) sorts for small input sizes. This may seem surprising given that merge sort is an \(\Theta(n \log n)\) sorting algorithm. However, it is important to keep in mind that asymptotic analysis is only concerned with rates of growth. A \(\Theta(n \log n)\) algorithm will always be faster than a \(\Theta(n^2)\) algorithm eventually, but that doesn't mean the \(\Theta(n^2)\) algorithm can't be faster for small inputs. The following figure was created by timing merge sort and insertion sort on small randomly ordered arrays from size 2 to size 150:

Sort timings

As you can see, insertion sort is faster until around \(n = 100\). At that point, merge sort becomes faster and it remains faster for all larger inputs.

A a reminder, the following pseudocode describes the overall logic of the merge sort Algorithm:

merge_sort(sub-array)
    If sub-array is has more than one entry: 
        Recursively merge_sort the left half
        Recursively merge_sort the right half
        Merge the two sorted halves.

This logic recursively splits the original array into smaller and smaller sub-arrays until the recursion bottoms out at sub-arrays of size one. This means that every time a large array is sorted, there are many recursive calls to merge sort that have small input sizes. In light of the figure above, that approach doesn't make much sense: merge sort is not a competitive sorting algorithm on small inputs. It would make more sense to recursively break the input into smaller and smaller pieces until some threshold is reached, and then switch strategies to a sorting algorithm that is more efficient on those small inputs.

The following pseudocode describes this alternate approach:

merge_sort(sub-array)
    If sub-array is has fewer than MERGE_SORT_THRESHOLD entries:
        Sort the sub-array with insertion sort. 
    Otherwise: 
        Recursively merge_sort the left half
        Recursively merge_sort the right half
        Merge the two sorted halves.

Choosing an appropriate value for MERGE_SORT_THRESHOLD requires some experimentation. The point where the two lines cross represents the input size where the two sorts are equally fast. Switching strategies at that input size will result in no speedup at all. The only way to determine the best choice for MERGE_SORT_THRESHOLD is to systematically experiment with different values until we find the one that leads to the best overall sorting performance. For the purposes of this lab, we will switch strategies at input sizes of 16. Feel free to experiment with different values to see if you can improve the performance.

Test your implementation of mergeSort2 using the provided unit tests.

Part 4 - Evaluating Your Improvements

Submission

Submit a .zip file containing both MergeSortsImproved.java and the image of your final performance graph.

*The second approach has recently become popular. Both Python (starting in version 2.3) and Java (starting in version 7) use Timsort as their default sorting algorithm. Timsort is a modified version of merge sort that includes several enhancements: it uses a more space-efficient merge operation, it takes advantage of partially sorted arrays by finding and merging existing sorted regions, and it uses a non-recursive binary insertion sort to handle short unsorted regions.