Sorting Algorithms
In Chapter 2 you learned about two Sorting Algorithms: Insertion Sort and Merge Sort. The textbook claims that these algorithms run in O(n^2) and O(nlogn),
respectively. However, because of our natural skepticism as a Software Developers, we must test those claims. To this end, you will implement (or download) code in
your favorite computer language for both sorting algorithms and actually run them in order to track their running times across different input arrays.
Your task is to run each algorithm 3 times on 5 input arrays with 5, 50, 500, 5000, and 50000 random integers each, and report their running times both as a table and
“n vs. time” plots.
Your table should look like this:
run# | n | algorithm | time
1 | 5 | Insertion Sort | 0.20sec
2 | 5 | Insertion Sort | 0.23sec
3 | 5 | Insertion Sort | 0.19sec
4 | 50 | Insertion Sort | 2.86sec
… … .. ..
29 | 50000 | Merge Sort | 28.34sec
30 | 50000 | Merge Sort | 25.57sec
Your charts should look somewhat like the following:
Finally, answer the question: Does the claim in the book about the algorithms’ efficiency match your observations? Explain.
Hints:
– If you decide to implement these algorithms yourself, follow their pseudo-codes as described in Chapter 2.
– Every language has a library that allows timing a piece of code. For example: C++ has time.h and ctime.h; Java has System; Python has time.py.
– You can easily build both the table and the plot using MS Excel or any other spreadsheet software.
– If you can’t figure out how to plot a table or the plots automatically, draw them on paper and post pictures of them
