The following exercise will compare the performance of sorting algorithms.

Implement standard Quicksort $($where the pivot is the element with index $0),$ as well as randomized Quicksort $($where the pivot is a random element$).$ Implement both Quicksort algorithms using auxiliary arrays to perform the partition.

Implement Mergesort.

Compare the performance of all three sorting algorithms. Which performs best and under what inputs? Provide an explanation. Compare the performance of the algorithms using the following three different types of data sets as follows: Let $n$ be the input size. Consider $n=32,64,128,256,512($i$.$e$.,5$ different input sizes$).$ For each input size, generate an array arr of the following three types:

arr$=[n,n-1,$dots,$3,2,1]($i$.$e$.,$ the numbers from $1$ to $n$ in reverse sorted order$).$

arr is a random permutation of $1,2,$dots,$n$

arr$=[1,3,$dots,$n-1,2,4,$dots,$n]($i$.$e$.,$ the odd numbers from $1$ to $n$ in increasing order followed by the even numbers from $1$ to $n$ in increasing order$).$

Present the results $($i$.$e$.,$ the execution time$)$ of these algorithms in a table.

Execution Time

$n$

Standard Quicksort

Randomized Quicksort

Mergesort