2. QuickSort
QuickSort is a divide and conquer algorithm.
It picks an element as a pivot and partitions the given array around the picked pivot.
There are many different versions of quickSort that pick pivot in different ways:
Always pick the first element as a pivot
Always pick the last element as a pivot
Pick a random element as a pivot
Pick median as a pivot
Here we will be picking the last element as a pivot.
The key process in quickSort is partition().
Target of partitions is, given an array and an element x of array as a pivot, put x at its correct position in a sorted array and put all smaller elements (smaller than x) before x, and put all greater elements (greater than x) after x.
All this should be done in linear time.