Lab 11: Sorting

Bubble and Merge sort timing comparison

In this lab, you will implement Bubble Sort (O(n²)) and run timing experiments to see how it compares to another algorithm called Merge Sort (O(n log₂ n)).

Download lab11.cpp from here. Implement the bubbleSort(...) function.

In Excel, Google Sheets, or something similar, make a spreadsheet with the following columns:

• list size
• Bubble Sort CPU time
• Merge Sort CPU time

Now run the Lab 11 program with different size lists. For each size, record the size and the average CPU time reported at the end of the 10 trials. After running a number of sizes (a dozen or so), make a line graph of your table with size on the x-axis, CPU time on the y-axis, and a separate line for each of the two sorting algorithms. As you increase the size, what do you notice?

Submit your code and your spreadsheet with graph to Canvas here.