Algorithm: Difference between Quick Sort and Merge Sort

1. Merge Sort is stable sort however Quick is not.
2. Worst case complexity for merge is O(nlogn) however for quick it is o(n*n)
3. Merger requires O(n) extra space for merging, however Quick does in place sorting.
4. Merge works well with all sizes of array, however Quick is good for smaller arrays for larger arrays it is inefficient as it does lots of comparison.
5. The Quick is internal nature means sorting happens in memory however Merge sort happens in auxiliary space i.e. it is external in nature.

Algorithm: Merge Sort

Merge Sort is again a way to sort array of elements. It is same as quick sort with small difference.

It works on Divide and Conquer algorithm.

It recursively divide array in 2 parts and once division reached the smallest unit, start merging the left and right arrays of middle elements in sorted way.

So basically while merging back the elements it does the comparison, that's the reason it is called merge sort.

Few Points:

1. It sorts using merging so it require extra space equivalent to the size of input array to keep elements temporary for merging. so its space complexity is O(n)
2. It always divides array in 2 parts using middle element.
3. Its worst and best case time complexity is O(nlogn).

package madwani.sushil.sorting;

import madwani.sushil.Util;

public class MergeSort {

    public static void main(String[] args) {

        String input = Util.readLine();

        int[] elements = Util.convertLineToIntArray(input);

        mergesort(elements, 0, elements.length-1);

        Util.print1dArray(elements);
    }

    public static void mergesort(int[] arr, int start, int end) {

        if(start < end) {

            int middle = ( start + end ) /2;

            mergesort(arr, start, middle);

            mergesort(arr, middle + 1, end);

            merge(arr, start, end, middle);

        }
    }

    private static void merge(int[] arr, int start, int end, int middle) {

        // left array size to keep left side elements

        int leftArrayLength = middle - start + 1;

        // right array size to keep right side elements
        int rightArrayLength = end - middle;

        int[] tempLeft = new int[leftArrayLength];

        int[] tempRight = new int[rightArrayLength];

        // temporary populate temp left array with left elements

        for ( int i =0; i< leftArrayLength ;i++) {
            tempLeft[i] = arr[start + i];

        }        // temporary populate temp right array with right elements

        for ( int i =0; i< rightArrayLength ;i++) {

            tempRight[i] = arr[middle + i + 1 ];
        }

        //lets actual merge start

        // i for left array
        // j for right array
        // k for merged array

        int i = 0, j = 0, k = start;

        while(i < leftArrayLength && j < rightArrayLength ) {

            // if left element is lesser than right element

            if(tempLeft[i] <= tempRight[j]) {
                arr[k] = tempLeft[i];
                i++;
            } else{
                // if right element is lesser than left element
                arr[k] = tempRight[j];
                j++;
            }
            k++;]
        }

        // populate remaining left element 

        while(i< leftArrayLength) {

            arr[k] = tempLeft[i];
            k++;i++;
        }

        // populate remaining right element 

        while(j< rightArrayLength) {
            arr[k] = tempRight[j];

            k++;j++;
        }
    }
}

Algorithms: QuickSort

Quicksort as name suggests is the one of the quick technique to sort array of elements.

Now Question is, is it the best one ? No, not at all, we have many other sorting algorithms better than it.

Still you should have a very good understanding of Quicksort.

Quicksort works on the Divide and Conquer strategy. 

It divides the whole array around an element of the array (we will call it Pivot), and try to arrange the elements in such a way that elements to the left of the array are smaller than it (might not be sorted) and elements to the right of Pivot are all greater than it    (might not be sorted).

Once you finish this activity, you are sure that the Pivot element is at the right position in the array.

Do the same to the left and right subarrays around the Pivot element recursively and you are done.

Just before moving to the code:
1. I have explained every step as comments in the code, so please read process in code only.

2. We can select any element as Pivot, it could be 1st element, last element or middle or any random. generally I choose middle, however it is not the most efficient.

3. When we write any recursive method we always have to think before hand when to break the recursion, so have this in mind.

4. Best case time complexity is O(nlogn)

5. Worst case time complexity is O(n*n) in case of worst choice of pivot or already sorted.

6. in Java 8, Quicksort is used for primitive elements array, however Mergesort is used for Objects array.

Github link

lets write some code:

package madwani.sushil.sorting;

import madwani.sushil.Util;

public class QuickSort {

    public static void main(String[] args) {

        String input = Util.readLine();

        int[] elements = Util.convertLineToIntArray(input);

        quicksort(elements, 0, elements.length-1);

        Util.print1dArray(elements);

    }

    public static void quicksort(int[] arr, int start, int end) {

        // basic check to ensure corner case

        if (arr == null || arr.length == 0) {

            return;

        }

        // condition to break recursion

        if (start >= end) {

            return;

        }

        // I always chose middle element as Pivot

        int middle = start + (end - start) / 2;

        // Pivot element

        int pivot = arr[middle];

        // lets start the real sorting

        int i = start, j = end;

        // do comparison and swapping till start and end have not met

        while (i <= j) {

            // increment till left side elements are lesser or equal to pivot

            while (arr[i] <= pivot) {

                i++;

            }

            // decrement till right side elements are greater to pivot

            while (arr[j] > pivot) {

                j--;

            }

            // swap elements from left right only when indices haven't crossed each other

            // after swap always increase lower index and decrease higher index

            if (i <= j) {

                Util.swapElementsInArray(arr, i, j);

                i++;

                j--;

            }

        }

        // one pass is done, so we have 2 boundaries
        // lower boundary: i which was moving towards end
        // upper boundary: j which was moving towards start



        // if i has not reached and crossed the end lets do one more pass from i to end
        // this is left subarray

        if (end > i) {
            quicksort(arr, i, end);
        }

        // if j has not reached the start and crossed, lets do one more pass from start to j
        // this is right subarray

        if (start < j) {
            quicksort(arr, start, j);
        }
    }
}