Merge Sort and Quick Sort!
Tags: algorithms, java, beginners, programming
Published: 2021-10-25 19:51:09

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.
![Gif](https://media.giphy.com/media/3o6Zt5jXXzAzdikVmE/giphy.gif)

## 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
![Merge](https://media.giphy.com/media/D0WOL0ogZIoG4/giphy.gif)
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**
```java
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))
```
### Pass copy of original array
```java
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);
    }
}
```
### In place
```java

public class MergeSort {
    public static void main(String[] args) {
        int[] arr = {4, 6, 2, 0, 1, 3};
        mergeSortInPlace(arr, 0, arr.length - 1);
        for (int a : arr)
            System.out.print(a + " ");
    }

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

        if (start < end) {
            int mid = start + (end - start) / 2;

            mergeSortInPlace(arr, start, mid);
            mergeSortInPlace(arr, mid + 1, end);
            merge(arr, mid, start, end);
        }
    }

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

        int l = start, r = mid + 1, i = 0;

        int[] mix = new int[end - start + 1];
        while (l <= mid && r <= end) {
            if (arr[l] <= arr[r]) {
                mix[i++] = arr[l];
                l++;
            } else {
                mix[i++] = arr[r];
                r++;
            }
        }
        while (l <= mid) {
            mix[i++] = arr[l++];
        }

        while (r <= end) {
            mix[i++] = arr[r++];
        }

        for (int k = 0; k < mix.length; k++) {
            arr[start + k] = mix[k];
        }

    }
}
```

## Dry Run
![Dry Run](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/dxz1eeq3xmn1pioem055.jpg)

## 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](https://media.giphy.com/media/jS2Wv3E0xSiquMLPcA/giphy.gif)
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 last 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] (It's not recommended that left or right side will sorted it might be possible but not necessary)

## Take pivot as an end element
```java

public class QuickSort {
    public static void quickSort(int [] nums, int start, int end) {
        if (start <  end) {
            int partitionIndex = partition(nums, start, end);
            quickSort(nums, start, partitionIndex - 1);
            quickSort(nums, partitionIndex + 1, end);
        }
    }

    public static int partition(int [] nums, int start, int end) {
        int pivot = nums[end];
        int partitionIndex = start;
        for (int i=start; i<end; i++) {
            // lesser than pivot
            if (nums[i] <= pivot) {
                swap(nums, i, partitionIndex);
                partitionIndex += 1;
            }
        }
        swap(nums, end, partitionIndex);
        return partitionIndex;
    }

    public static void swap(int [] nums, int i, int j) {
        int temp = nums[i];
        nums[i] = nums[j];
        nums[j] = temp;
    }

    public static void main(String [] args) {
        int [] nums = {5, 3, 2, 12, 100, 11, 1, 5, 6, 7,83, 4, 45, 56, 7, 4, 3,1};
        quickSort(nums, 0, nums.length - 1);
        for (int number : nums) {
            System.out.print(number + " ");
        }
    }
}
```
## Take pivot as a middle element
```java
package com.example.helloworld;

public class QuickSort {
    public static void quickSort(int [] nums, int start, int end) {
       if(start >= end)return;
       int left = start, right = end;
       int mid = start + (end - start) / 2;
       int pivot = nums[mid];
       while(left <= right){

           while(nums[left] < pivot)left++;
           while(nums[right] > pivot)right--;

           if(left <= right) {
               swap(nums, left, right);
               left++;
               right--;
           }
       }
      //now my pivot at its correct position so, apply same for the two halves recursively!
       quickSort(nums, start, right);
       quickSort(nums, left, end);
    }

    public static void swap(int [] nums, int i, int j) {
        int temp = nums[i];
        nums[i] = nums[j];
        nums[j] = temp;
    }

    public static void main(String [] args) {
        int [] nums = {5, 3, 2, 12, 100, 11, 1, 5, 6, 7,83, 4, 45, 56, 7, 4, 3,1};
        quickSort(nums, 0, nums.length - 1);
        for (int number : nums) {
            System.out.print(number + " ");
        }
    }
}
```




## Useful link
- [Sorting](https://github.com/SUCHITRAGIRI/DailyCodeWithJava/tree/main/Sorting)

##Hope it helps, please share your thoughts in the comments ☺️