Like merge sort, quick sort also uses the divide and conquer approach to sort the given array or list. In quick sort, the sorting of an array is achieved by taking an element from the input array as the pivot and then split the array using the pivot.

Algorithm

STEP 1: Take either the first or the last element as the pivot element.

STEP 2: Find and place the pivot element at its correct position, i.e., the elements that are on the left side of the pivot element must be less than the pivot element. Also, elements that are on the right side of the pivot element must be greater than the pivot element.

STEP 3: Recursively execute steps 1 and 2 till the whole array is sorted.

Pseudo Code

// start → Beginning index, end → Last index

quickSort(arr[], start, end)

{

if(start >= end) return; // base case

else

{

// The partition() method positions the pivot

// at the right place, i.e., left side of pivot contains

// elements that are less than pivot and right side of

// pivot contains elements that are greater than pivot

pivot = partition(arr, start, end);

// Invoking the method quickSort() for the left side of pivot

quickSort(arr, start, pivot — 1);

// Invoking the method quickSort() for the right side of pivot

quickSort(arr, pivot + 1, end);

}

}