Data Structure & Algorithms : Sorting

Quick Sort:

public class Quick {
    public void quickSort(int[] A) {
        if (A == null || A.length <= 1) {
            return;
        }
        
        //Collections.shuffle(A);
        quickSortHelper(A, 0, A.length - 1);
    }

    private void quickSortHelper(int[] A, int lo, int hi) {
        if (lo >= hi) {
            return;
        }

        int j = partition(A, lo, hi);
        quickSortHelper(A, lo, j - 1);
        quickSortHelper(A, j + 1, hi);
    }
    
     //  partition the subarray a[lo..hi] so that a[lo..j-1] <= a[j] <=
     //  a[j+1..hi]
     //  and return the index j.
    private int partition(int[] A, int lo, int hi) {
        int pivot = A[lo];
        int i = lo + 1;
        int j = hi;

        while (i <= j) {
            while (i <= j && A[i] < pivot) {
                i++;
            }

            while (i <= j && A[j] > pivot) {
                j--;
            }
            if (i <= j) {
                swap(A, i, j);
            }
        }

        // swap the pivot 
        swap(A, lo, j);

        return j;
    }

    private void swap(int[] A, int i, int j) {
        int temp = A[i];
        A[i] = A[j];
        A[j] = temp; 
    }
    
    public static void main(String[] args) {
         int[] A = new int[]{-5,4,2,-6};

         Quick quick = new Quick();
         quick.quickSort(A);

         for (int i = 0; i < A.length; i++) {
            System.out.print(A[i] + " ");
         }

         System.out.println();
    }
}

Follow-up:
When is the quick sort has time complexity of O(n^2)?

The Quick sort performs worst ie, at O(n^2) when all the values of the pivot chosen is either the largest or smallest of the taken set. Consider this example.

1 2 3 4 5

The pivot chosen say is 1, you will have 4 elements on the right side of the pivot and no elements on the left side. Applying this same logic recursively and the pivot chosen is 2, 3, 4, 5 respectively, we have attained a situation where this sort has performed at its worst possible time.

It has been recommended and proven that Quicksort performs well if the input is shuffled well.

Moreover, selection of a sort usually depends on a clear knowledge about the input domain. For example, if the input is huge, then there is something called as external sort which may use external memory. If the input size is very small, we may go for a merge sort but not for medium and huge input sets since it uses extra memory. The main advantage of Quick sort is its "in-place"ness meaning, no extra memory is being used for the input data. Its worst case time on paper is O(n^2) but still is widely preferred and used. My point here is, sorting algorithms can be changed based on the knowledge on the input set and its a matter of preference.

Merge Sort:

public class MergeSort {
    public void mergeSort(int[] A) {
        if (A == null || A.length <= 1) {
            return;
        }
        
        int[] Aux = new int[A.length];

        divide(A, Aux, 0, A.length - 1);
    }

    private void divide(int[] A, int[] Aux, int lo, int hi) {
        if (lo >= hi) {
            return;
        }

        int mid = lo + (hi - lo) / 2;

        divide(A, Aux, lo, mid);
        divide(A, Aux, mid + 1, hi);

        merge(A, Aux, lo, mid, hi);
    }

    private void merge(int[] A, int[] Aux, int lo, int mid, int hi) {
        // copy A to Aux
        for (int k = lo; k <= hi; k++) {
            Aux[k] = A[k];
        }

        int i = lo;
        int j = mid + 1;

        for (int k = lo; k <= hi; k++) {
            if (i > mid) {
                A[k] = Aux[j++];
            } else if (j > hi) {
                A[k] = Aux[i++];
            } else if (Aux[i] <= Aux[j]) {
                A[k] = Aux[i++];
            } else {
                A[k] = Aux[j++];
            }
        }
    }

    public static void main(String[] args) {
         int[] A = new int[]{3,1};

         MergeSort merge = new MergeSort();
         merge.mergeSort(A);

         for (int i = 0; i < A.length; i++) {
            System.out.print(A[i] + " ");
         }

         System.out.println();
    }
}