QuickSort Algorithm

Quicksort or partition-exchange sort, is a fast sorting algorithm, which is using divide and conquer algorithm. 
Quicksort first divides a large list into two smaller sub-lists: the low elements and the high elements. Quicksort 
can then recursively sort the sub-lists. On the average, it has O(nlogn) complexity, making quicksort 
suitable for sorting big data volumes.

Algorithm:
1) If the array contains only one element or zero elements then the array is sorted.
2) Choose an element, called pivot, from the list. Generally pivot can be the middle index element.
3) Reorder the list so that all elements with values less than the pivot come before the pivot, while all 
   elements with values greater than the pivot come after it (equal values can go either way). After this 
   partitioning, the pivot is in its final position. This is called the partition operation.
4) Recursively apply the above steps to the sub-list of elements with smaller values and separately the sub-list 
   of elements with greater values.

============================QuickSort Start===========================
package algorithm;
public class QuickSort {
    static int[] array= {2,3,45,65,31,32,90,5,6,9};
    
    public static void main(String[] args) {
        for(int i=0;i<array.length;i++) {
            System.out.print(array[i]+", ");
        }
        System.out.println("");
        QuickSort sorter = new QuickSort();
        sorter.quicksort(0, array.length-1);
        System.out.println("Sorted array: ");

        for(int i=0;i<array.length;i++) {
            System.out.print(array[i]+", ");
        }
    }    
    private void quicksort(int arrayMinPosition, int arrayMaxPosition) {  //Initially 0 and 9  (0, array.length-1)
        if (array ==null || array.length==0){
            return;
        }
        int i = arrayMinPosition, j = arrayMaxPosition;
        //int pivot = array[(arrayMinPosition+arrayMaxPosition)/2]; //Get the Pivot element from middle of the array.
        //For small arrays above getting above line for pivot is good. For very large arrays, sum of arrayMinPosition+arrayMaxPosition 
        //may result in overflow, hence the below approach. Because arrayMinPosition and arrayMaxPosition will be changing everytime.
        
        int pivot = array[arrayMinPosition+(arrayMaxPosition-arrayMinPosition)/2];         
        System.out.println("Pivot Element: "+pivot);

        while (i <= j) {                //Divide into two arrays and compare with Pivot element.
            while (array[i] < pivot) {  //Compare first sub-array elements with Pivot, if less, continue..
                i++;
            }
            while (array[j] > pivot) {  //Compare second sub-array elements with Pivot, if greater, continue..
                j--;
            }            
            if (i <= j) {  //We need to swap the values as the above 2 while loop cases have been executed.
                int temp = array[i];
                array[i] = array[j];
                array[j] = temp;
                i++;
                j--;
            }
        }
        //Using Recursion
        if (arrayMinPosition < j)
            quicksort(arrayMinPosition, j);
        if (i < arrayMaxPosition)
            quicksort(i, arrayMaxPosition);
    }
}
============================QuickSort End===========================
//Output:
2, 3, 45, 65, 31, 32, 90, 5, 6, 9, 
Pivot Element: 31
Pivot Element: 9
Pivot Element: 3
Pivot Element: 5
Pivot Element: 31
Pivot Element: 32
Pivot Element: 65
Sorted array: 
2, 3, 5, 6, 9, 31, 32, 45, 65, 90, 

On an average Quicksort Algorithm has the complexity of O(nlogn) and in the worst case it has O(n²) when the 
elements of the input array are already sorted in ascending or descending order.
Good thing about Quicksort is that it's an in place algorithm, which means it does not takes any additional space, 
except those used by method stack memory. 
Arrays.sort() method in Java use quicksort to sort array of primitives e.g. array of integers or array of float numbers 
and uses Mergesort to sort objects e.g. array of String.

The 'logn' part comes from the fact that it's (at least ideally) breaking the input in half at each iteration. Starting 
from N items, and breaking those in half each time means that you're down to 1 item after log2(N) iterations, at which 
point you obviously can't subdivide it any further. For example, starting from, say, 128 items, you divide into groups 
of 64, 32, 16, 8, 4, 2, 1 items -- 7 iterations (and log2(128) = 7).

Each of those iterations scans through the entire array to partition it, so you end up with O(log N) operations, each 
of which has O(n) complexity, for O(nlogn) overall complexity.

To be technically correct, the Big-O is O(N2). This arises from the fact that a sufficiently bad choice of partition 
element could split the array into one element on one side, and the entire rest of the array on the other. If this 
happens at every iteration, it takes N iterations to split it down into pieces of one element apiece, so you get N 
operations, each with a complexity of O(N), for O(N * N) overall.

In worst case if you choose the smallest or the largest element as the pivot then the time will be O(n^2).
O(log n) generally means you can cut the dataset in half with each iteration (e.g. binary search)
O(n log n) means you're performing an O(log n) operation for each item in your dataset.