Sorting Algorithms Elapsed Time Comparison
The purpose of this homework is to observe how running times of different sorting algorithms grow as the input size grows. As the requirement, I randomly generated 10K to 100K integer to test with and use the current time in milliseconds to measure the elapsed time.
Per homework requirements, I implemented 4 sorting algorithms including insertion sort, merge sort, quick sort and heap sort. According to Goodrich, M. T., & Tamassia, R. (2015), the running times of insertion sort is O(n^2); the running times of merge sort is O(nlogn); on average, the running times of the quick sort is O(nlogn), but in the worst case, it can be O(n^2); the running times of heap sort is O(nlogn).
Reference:
Goodrich, M. T., & Tamassia, R. (2015). Data structures and algorithms in Java. New York: John Wiley.
http://javabypatel.blogspot.in/2015/11/heap-sort-algorithm.html
http://javabypatel.blogspot.in/2015/11/heap-sort-algorithm.html
http://tufangorel.blogspot.com/2015/10/generic-recursive-merge-sort-in-java.html