The running time of quicksort can be improved in practice by taking advantage of the fast running time of insertion sort when its input is ”nearly” sorted. When quicksort is called on a subarray with fewer than k elements, let it simply return without sorting the subarray. After the top-level call to quicksort returns, run insertion sort on the entire array to finish the sorting process. Argue that this sorting algorithm runs in O(nk + n log(n/k)) expected time. How should k be picked, both in theory and in practice ?

Sorting Algorithms

The goal here is a comparative experimental study, in terms of running time, of the following sorting algorithms.

• Insertion sort.

• Mergesort.

• Quicksort.

• Quicksort as shown in exercise above (we will call this algorithm Quick-insertion).

1. Implement these algorithms above within the same program. The input and output are described as follows.

Input: 2 parameters N (number of random naturals to sort) and K (used by Quick-insertion).

Output: Display the list of N randomly generated naturals. For each algorithm display the list of sorted numbers + corresponding running time.

2. Find the pair of values (N, K) where :

(a) Quick-insertion outperforms all the other algorithms.

(b) Insertion sort outperforms all the other algorithms.

(c) Quicksort outperforms all the other algorithms.

**Subject Computer Science C-Family Programming**