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))
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);
}
}
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];
}
}
}
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 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
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 + " ");
}
}
}
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 + " ");
}
}
}
Top comments (3)
Sharing my code for the quicksort
Thanks for sharing!
Will add this:)
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