## DEV Community is a community of 757,421 amazing developers

We're a place where coders share, stay up-to-date and grow their careers. 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. ## 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 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 + " ");
}
}
}
``````

## 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 + " ");
}
}
}
``````

## Discussion (3) 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 + " ");
}
}
}
`````` 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