CSCI 200 - Summer 2023
Foundational Programming Concepts & Design

Lab 6A - Merge Sort

This lab is due by Thursday, May 04, 2023, 11:59 PM.
As with all labs you may, and are encouraged, to pair program a solution to this lab. If you choose to pair program a solution, be sure that you individually understand how to generate the correct solution.

Instructions

For this lab, add to your abstract List class a purely virtual void sort() method. This function will need to be implemented as both Array::sort() and LinkedList::sort(). Both of these implementations will perform the recursive Merge Sort algorithm.

To test your implementations, perform the following steps for each List implementation:

  1. Create a list of integers
  2. Populate the list with the values in order: 4 3 8 1 5 9 7 2 6
  3. Print the list forwards (prints 4 3 8 1 5 9 7 2 6)
  4. Sort the list
  5. Print the list forwards (prints 1 2 3 4 5 6 7 8 9)

To assist with the debugging of the recursive steps, have each function call print out the contents of the left and right lists after splitting. Additionally, print out the contents of the resultant merged list each function call.

You are encouraged to test your sorting with other list contents to verify its correctness (such as a list of strings).

An example run of the program may be: 

Sorting an array:
Initial array: 4 3 8 1 5 9 7 2 6
Left:  4 3 8 1 5
Right: 9 7 2 6
Left:  4 3 8
Right: 1 5
Left:  4 3
Right: 8
Left:  4
Right: 3
Merged: 3 4
Merged: 3 4 8
Left:  1
Right: 5
Merged: 1 5
Merged: 1 3 4 5 8
Left:  9 7
Right: 2 6
Left:  9
Right: 7
Merged: 7 9
Left:  2
Right: 6
Merged: 2 6
Merged: 2 6 7 9
Merged: 1 2 3 4 5 6 7 8 9
Sorted array: 1 2 3 4 5 6 7 8 9

When it's verified the sorting algorithm is operating correctly, remove the debugging outputs to clean up the generated output. Now the example run would be similar to below: 

Sorting an array:
Initial array: 4 3 8 1 5 9 7 2 6
Sorted array: 1 2 3 4 5 6 7 8 9

Sorting a Linked List:
Initial list: 4 3 8 1 5 9 7 2 6
Sorted list: 1 2 3 4 5 6 7 8 9

Sorting a Linked List:
Initial list: dog cat bird elephant
Sorted list: bird cat dog elephant

Lab Submission

Submit your main.cpp, Makefile, List.hpp, Array.hpp, LinkedList.hpp file(s).

You will submit your solution to this lab with the rest of Set6. Detailed instructions for doing this are posted in Assignment 6.


This lab is due by Thursday, May 04, 2023, 11:59 PM.
As with all labs you may, and are encouraged, to pair program a solution to this lab. If you choose to pair program a solution, be sure that you individually understand how to generate the correct solution.