DEV Community

Cover image for Merge Sort and Quick Sort!
Suchitra
Suchitra

Posted on • Updated on

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.
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
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))
Enter fullscreen mode Exit fullscreen mode

Pass copy of original array

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);
    }
}
Enter fullscreen mode Exit fullscreen mode

In place


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];
        }

    }
}
Enter fullscreen mode Exit fullscreen mode

Dry Run

Dry Run

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
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

Take pivot as an end element


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 + " ");
        }
    }
}
Enter fullscreen mode Exit fullscreen mode

Take pivot as a middle element

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 + " ");
        }
    }
}
Enter fullscreen mode Exit fullscreen mode

Useful link

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

Discussion (3)

Collapse
rohithv07 profile image
Rohith V

Sharing my code for the quicksort

import java.util.*;

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 + " ");
        }
    }
}
Enter fullscreen mode Exit fullscreen mode
Collapse
suchitra_13 profile image
Suchitra Author

Thanks for sharing!
Will add this:)

Collapse
zyabxwcd profile image
Akash • Edited on

reminded me of college days :) btw you should check out educative.io. you seem interested in dsa. i am sure you will find it as a great resource if not known already