Quicksort

Introduction

Quicksort is the fastest known comparison-based sorting algorithm for arrays in the average case.

Caveat: Merge sort works better on linked lists, and there are other non-comparison based algorithms that outperform quicksort.

Quick sort algorithm

1. Start with an array of n elements.

2. Choose a pivot element from the array to be sorted.

3. Partition the array into two unsorted subarrays, such that all elements in one subarray are less than the pivot and all the elements in the other subarray are greater than the pivot.

4. Elements that are equal to the pivot can go in either subarray.

5. Sort each subarray recursively to yield two sorted subarrays.

6. Concatenate the two sorted subarrays and the pivot ...