Merge Sort and Quick Sort!

In this article I am going to explain two sorting algorithms, Merge Sort and Quick Sort with detailed analysis, application and space and time complexity.

Before starting the topic, let's know about basic and other sorting algorithms.

Some Sorting Algorithms are

• Bubble Sort

Easy to implement and easy to understand. But not efficient sort, it takes O(N^2) time complexity and O(1) space. Means it is an in place sorting algorithm.(In each iteration, the biggest element goes into its correct position and in single iteration we have to do more number of swaps).

• Selection Sort
  Less number of swaps as compared to Bubble Sort. But still not efficient.
  It is an in place and unable sorting algorithm with O(N^2) time complexity.

• Insertion Sort

It also takes O(N^2) time complexity, but the interesting part of this sorting algorithm is that it takes just O(N) when the elements are partially sorted.
In place and stable sorting, algorithm.

• Heap Sort
  It is an unstable sorting with O(NlogN) time and O(1) space complexity.

• Count Sort

It is a stable sorting algorithm with time complexity O(N + K) where n is the number of elements in the array and k is the range of the elements. Counting sort is most efficient if the range of input values is not greater than the number of values to be sorted. Space O(N + K).
arr = [3, 2, 4, 1, 2] here N = 5, k = 4 - 1 = 3
range of input(N) < number of elements(K)
If range is lager, then it will be not efficient to use.

Now it's time to explain about Merge and Quick sort...

Merge Sort

It is based on Divide and Conquer technique with worst-case time complexity O(NlogN), it is one of most respective algorithms.

Merge Sort first divides the array into equal halves and then merging them in a sorted manner.

Algorithm

Step 1: If only one element in the list, return it.Step 2: Divide the list recursively into two halves until it can no more divided.Step 3: Merge the smaller lists into new lists in sorted order(start comparing the elements from two halves of the list, and choose smaller element each time between them and store it into another list(extra space))

Code

import java.util.*;class Solution {    public int[] merge_sort(int[] input) {        if (input.length <= 1) {            return input;        }        int pivot = input.length / 2;        int[] left_list = merge_sort(Arrays.copyOfRange(input, 0, pivot));        int[] right_list = merge_sort(Arrays.copyOfRange(input, pivot, input.length));        return merge(left_list, right_list);    }    public int[] merge(int[] left_list, int[] right_list) {        int[] ret = new int[left_list.length + right_list.length];        int left_cursor = 0, right_cursor = 0, ret_cursor = 0;        while (left_cursor < left_list.length && right_cursor < right_list.length) {            if (left_list[left_cursor] < right_list[right_cursor]) {                ret[ret_cursor++] = left_list[left_cursor++];            } else {                ret[ret_cursor++] = right_list[right_cursor++];            }        }        // append what is remain the above lists        while (left_cursor < left_list.length) {            ret[ret_cursor++] = left_list[left_cursor++];        }        while (right_cursor < right_list.length) {            ret[ret_cursor++] = right_list[right_cursor++];        }        return ret;    }}class MergeSort {    public static void main(String args) {        Scanner sc = new Scanner(System.in);        int n = sc.nextInt();        int[] arr = new int[n];        for (int i = 0; i < n; i++) {            arr[i] = sc.nextInt();        }        // call merge sort function        arr = merge_sort(arr);        System.out.print(arr);    }}

Pros and Cons

Pros

• Large size list merged by this sort.
• Also used in linked list.
• External sorting
• Stable
• Time efficient O(NlogN)

Cons

• It takes extra space Need space in the stack(Recursive) logN and extra space N.O(N + logN)= O(N)
• Not much efficient for small problem

Quick Sort

Quick sort uses the partition algorithm for finding pivot element and divide the array recursively into two halves.

The idea behind this algorithm is that it is a similar kind of merge sort, but it does not take extra space. Here, the pivot element plays a major role.

What is a pivot element?

• choose pivot as 1st element
• choose pivot as 2nd element
• choose pivot as middle element (Best way)
• choose pivot as random element (Best way)

Logic:

Suppose arr = [5, 3, 1, 2, 4]
Step 1: Choose pivot element (took pivot as random so, pivot = 3)
Step 2: In one pass we find pivot is in its proper position, means all the elements which are smaller than pivot are placed in left side and all the elements which are greater than pivot placed right side.(some logic are applied to do so)
Now the array is : 2, 1, 3, 5, 4

Useful link

• Sorting

Hope it helps, please share your thoughts in the comments