C++ Quick Sort

Write a program to sort an array of 100,000 random elements using quicksort as follows:

• Sort the arrays using pivot as the middle element of the array
• Sort the arrays using pivot as the median of the first, last, and middle elements of the array
• Sort the arrays using pivot as the middle element of the array. However, when the size of any sub-list reduces to less than 20, sort the sub-list using insertion sort.
• Sort the array using pivot as the median of the first, last, and middle elements of the array, When the size of any sub-list reduces to less than 20, sort the sub-list using insertion sort.
• Calculate and display the CPU time for each of the preceding four steps.

Example of the median of the first, last and middle elements:

1 2 3 4 5 6 7 8 0 (median of 1, 5, 0, is 1)
8 0 1 2 3 4 5 6 7 (median of 8, 3, 7, is 7)

To calculate the CPU time, use the header and clock_type. Depends on the CPU of your computer, your number would not be the same as in the sample output below.

Sample output:

Array size = 100000
Quick sort time, with pivot middle element: 37
Quick sort time, with pivot median element: 35
Quick sort and insertion sort time, with pivot middle element: 37
Quick sort and insertion sort time, with pivot median element: 36

Array size = 300000
Quick sort time, with pivot middle element: 115
Quick sort time, with pivot median element: 115
Quick sort and insertion sort time, with pivot middle element: 110
Quick sort and insertion sort time, with pivot median element: 110