CS 161 Lab 14: Sorting

Overview

This lab will cover implementation and timing of various sorting algorithms.

Lab Assignment

You will need the following files:

Bubble sort and insertion sort have been done for you, you will just work on merge sort.

Explanation of Merge Sort

While sorting algorithms such as insertion, selection, or bubble sort work well enough for small amounts of data, they are too slow for large data sets. Merge sort is a more efficient sorting algorithm that can be implemented with recursion.

Given a list of items to sort, merge sort recursively divides the list into halves until the sublists are sufficiently small (for our purposes, this is size 1). Conceptually, you may imagine merge sort as creating a branching tree structure of lists. Once the size threshold is reached, sublists are then recursively merged in pairs to form a new list that is in sorted order. This is achieved by incrementally adding the smallest item from the heads of the two lists. Each sublist is independently in sorted order and can thus be easily merged by simply looking at the two leading elements.

Here is an example of merge sort in action (from Wikipedia):

A dancing example(from youtube):

Example of merge sort's recursively dividing a list into sublists of size 1. Sublists are then recursively merged in sorted order until a single list remains. This final list is in sorted order.

Implementing Merge Sort

Finish implementing MergeSort.sort(). This will use the Student.compareTo(Student other) method, which has been implemented for you. This sorts first by graduate level (undergrads go first), then by GPA (lowest to highest), then by name (A to Z). For this step, you should test on a small number of students. Use SortingTests main() to test your implementation. This will generate a random array of students, then use each of the sorting algorithms to sort the array. The sorted lists will be written to bubble_sort.txt, insertion_sort.txt, and merge_sort.txt. You should check the contents of merge_sort.txt in order to verify that your merge sort implementation is working correctly.

Steps/tips for merge sort:
1. If the array does not meet the base case (which is what, looking at the picture?), split it into two arrays, with the first half in one array and the second half in the other.
2. If you called the left array left, then assign left to what sort(left) returns. Do the same thing for right.
3. Call merge on the two halves. This method combines two sorted arrays into one array which is also sorted.

Comparing different search algorithms

After you have implemented merge sort, you should compare the performance of each of the three search algorithms for different numbers of students. Edit the numStudents array in SortingTests.main() to test different numbers of students. SortingTests uses the Stopwatch class to time the performance of each algorithm. For each element in the numStudents, a different sorting experiment will be run using that number of students. Try different numbers of students and observe how each search algorithm scales. Show your findings to the TA.