1. Merge Sort

merge sort example

The MergeSort function repeatedly divides the array into two halves until we reach a stage where we try to perform MergeSort on a subarray of size 1 i.e. p == r.

After that, the merge function comes into play and combines the sorted arrays into larger arrays until the whole array is merged.

Pseudocode:

1
2
3
4
5
6
7
MergeSort(A, p, r):
    if p > r 
        return
    q = (p+r)/2
    mergeSort(A, p, q)
    mergeSort(A, q+1, r)
    merge(A, p, q, r)

JAVA:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
// Merge two subarrays L and M into arr
void merge(int arr[], int p, int q, int r) { // r is the size of the array

    // Create L ← A[p..q] and M ← A[q+1..r]
    int n1 = q - p + 1;
    int n2 = r - q;

    int L[n1], M[n2];

    for (int i = 0; i < n1; i++)
        L[i] = arr[p + i];
    for (int j = 0; j < n2; j++)
        M[j] = arr[q + 1 + j];

    // Maintain current index of sub-arrays and main array
    int i, j, k;
    i = 0;
    j = 0;
    k = p;

    // Until we reach either end of either L or M, pick larger among
    // elements L and M and place them in the correct position at A[p..r]
    while (i < n1 && j < n2) {
        if (L[i] <= M[j]) {
            arr[k] = L[i];
            i++;
        } else {
            arr[k] = M[j];
            j++;
        }
        k++;
    }

    // When we run out of elements in either L or M,
    // pick up the remaining elements and put in A[p..r]
    while (i < n1) {
        arr[k] = L[i];
        i++;
        k++;
    }

    while (j < n2) {
        arr[k] = M[j];
        j++;
        k++;
    }
}

Merge( ) Function Explained Step-By-Step

Merging two consecutive subarrays of array

Merging two consecutive subarrays of array

The array A[0..5] contains two sorted subarrays A[0..3] and A[4..5]. Let us see how the merge function will merge the two arrays.

Step 2: Maintain current index of sub-arrays and main array

1
2
3
4
int i, j, k;
i = 0; 
j = 0; 
k = p;

Maintain indices of copies of sub array and main arrayMaintain indices of copies of sub array and main array

Step 3: Until we reach the end of either L or M, pick larger among elements L and M and place them in the correct position at A[p..r]

1
2
3
4
5
6
7
8
9
10
while (i < n1 && j < n2) { 
    if (L[i] <= M[j]) { 
        arr[k] = L[i]; i++; 
    } 
    else { 
        arr[k] = M[j]; 
        j++; 
    } 
    k++; 
}

Comparing individual elements of sorted subarrays until we reach end of oneComparing individual elements of sorted subarrays until we reach end of one

Step 4: When we run out of elements in either L or M, pick up the remaining elements and put in A[p..r]

1
2
3
4
5
6
7
// We exited the earlier loop because j < n2 doesn't hold
while (i < n1)
{
    arr[k] = L[i];
    i++;
    k++;
}

Copy the remaining elements from the first array to main subarrayCopy the remaining elements from the first array to main subarray

1
2
3
4
5
6
7
8
    // We exited the earlier loop because i < n1 doesn't hold  
    while (j < n2)
    {
        arr[k] = M[j];
        j++;
        k++;
    }
}

2. Quick Sort

1. Select the Pivot Element

There are different variations of quicksort where the pivot element is selected from different positions. Here, we will be selecting the rightmost element of the array as the pivot element.

Quick Sort StepsSelect a pivot element

2. Rearrange the Array

Now the elements of the array are rearranged so that elements that are smaller than the pivot are put on the left and the elements greater than the pivot are put on the right.

Quick Sort Steps

Here’s how we rearrange the array:

  1. A pointer is fixed at the pivot element. The pivot element is compared with the elements beginning from the first index.

    Quick Sort Steps

  2. If the element is greater than the pivot element, a second pointer is set for that element.

    Quick Sort Steps

  3. Now, pivot is compared with other elements. If an element smaller than the pivot element is reached, the smaller element is swapped with the greater element found earlier.

    Quick Sort Steps

  4. Again, the process is repeated to set the next greater element as the second pointer. And, swap it with another smaller element.

    Quick Sort Steps

  5. The process goes on until the second last element is reached.

    Quick Sort StepsThe process goes on until the second last element is reached.

  6. Finally, the pivot element is swapped with the second pointer.

    Quick Sort StepsFinally, the pivot element is swapped with the second pointer.

3. Divide Subarrays

Pivot elements are again chosen for the left and the right sub-parts separately. And, step 2 is repeated.

Quick Sort Steps

pseudocode

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
quickSort(array, p, r)
  if (p < r)
    pivotIndex = partition(array,p, r)
    quickSort(array, p, pivotIndex - 1)
    quickSort(array, pivotIndex, r)

partition(array, p, r)
  set r as pivotIndex
  storeIndex = p - 1
  for i = p + 1 to r
  if element[i] < pivotElement
    swap element[i] and element[storeIndex]
    storeIndex++
  swap pivotElement and element[storeIndex+1]
return storeIndex + 1

JAVA

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
// Quick sort in Java

import java.util.Arrays;

class Quicksort {

  // method to find the partition position
  static int partition(int array[], int low, int high) {
    
    // choose the rightmost element as pivot
    int pivot = array[high];
    
    // pointer for greater element
    int i = (low - 1);

    // traverse through all elements
    // compare each element with pivot
    for (int j = low; j < high; j++) {
      if (array[j] <= pivot) {

        // if element smaller than pivot is found
        // swap it with the greatr element pointed by i
        i++;

        // swapping element at i with element at j
        int temp = array[i];
        array[i] = array[j];
        array[j] = temp;
      }

    }

    // swapt the pivot element with the greater element specified by i
    int temp = array[i + 1];
    array[i + 1] = array[high];
    array[high] = temp;

    // return the position from where partition is done
    return (i + 1);
  }

  static void quickSort(int array[], int low, int high) {
    if (low < high) {

      // find pivot element such that
      // elements smaller than pivot are on the left
      // elements greater than pivot are on the right
      int pi = partition(array, low, high);
      
      // recursive call on the left of pivot
      quickSort(array, low, pi - 1);

      // recursive call on the right of pivot
      quickSort(array, pi + 1, high);
    }
  }
}

// Main class
class Main {
  public static void main(String args[]) {

    int[] data = { 8, 7, 2, 1, 0, 9, 6 };
    System.out.println("Unsorted Array");
    System.out.println(Arrays.toString(data));

    int size = data.length;

    // call quicksort() on array data
    Quicksort.quickSort(data, 0, size - 1);

    System.out.println("Sorted Array in Ascending Order: ");
    System.out.println(Arrays.toString(data));
  }
}

 3.Counting Sort

  1. Find out the maximum element (let it be max) from the given array.

Counting Sort steps

  1. Initialize an array of length max+1 with all elements 0. This array is used for storing the count of the elements in the array.

Counting Sort Step

  1. Store the count of each element at their respective index in count array

For example: if the count of element 3 is 2 then, 2 is stored in the 3rd position of count array. If element “5” is not present in the array, then 0 is stored in 5th position.

Counting Sort Step

4. Store cumulative sum of the elements of the count array. It helps in placing the elements into the correct index of the sorted array. (0, 0+1, 0+1+2, 0+1+2+2…..)

Counting Sort Step

  1. Find the index of each element of the original array in the count array. This gives the cumulative count. Place the element at the index calculated as shown in figure below.

Counting Sort Steps6. After placing each element at its correct position, decrease its count by one.

Pesudocode

1
2
3
4
5
6
7
8
9
10
11
countingSort(array, size)
  max <- find largest element in array
  initialize count array with all zeros
  for j <- 0 to size
    find the total count of each unique element and 
    store the count at jth index in count array
  for i <- 1 to max
    find the cumulative sum and !!!!!!! store it in count array itself !!!!!!
  for j <- size down to 1
    restore the elements to array
    decrease count of each element restored by 1

JAVA

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
// Counting sort in Java programming

import java.util.Arrays;

class CountingSort {
  void countSort(int array[], int size) {
    int[] output = new int[size + 1];

    // Find the largest element of the array
    int max = array[0];
    for (int i = 1; i < size; i++) {
      if (array[i] > max)
        max = array[i];
    }
    int[] count = new int[max + 1];

    // Initialize count array with all zeros.
    for (int i = 0; i < max; ++i) {
      count[i] = 0;
    }

    // Store the count of each element
    for (int i = 0; i < size; i++) {
      count[array[i]]++;
    }

    // Store the cummulative count of each array
    for (int i = 1; i <= max; i++) {    //notice, here i starts from 1
      count[i] += count[i - 1];
    }

    // Find the index of each element of the original array in count array, and
    // place the elements in output array
    for (int i = size - 1; i >= 0; i--) {
      output[count[array[i]] - 1] = array[i];
      count[array[i]]--;
    }

    // Copy the sorted elements into original array
    for (int i = 0; i < size; i++) {
      array[i] = output[i];
    }
  }

  // Driver code
  public static void main(String args[]) {
    int[] data = { 4, 2, 2, 8, 3, 3, 1 };
    int size = data.length;
    CountingSort cs = new CountingSort();
    cs.countSort(data, size);
    System.out.println("Sorted Array in Ascending Order: ");
    System.out.println(Arrays.toString(data));
  }
}

 4. Bucket Sort

The process of bucket sort can be understood as a scatter-gather approach. Here, elements are first scattered into buckets then the elements in each bucket are sorted. Finally, the elements are gathered in order.

Bucket Sort Working

!!!!!!!

  1. Suppose, the input array is:

    Bucket Sort StepsInput array

    Create an array of size 10. Each slot of this array is used as a bucket for storing elements.

    Bucket Sort StepsArray in which each position is a bucket

  2. Insert elements into the buckets from the array. The elements are inserted according to the range of the bucket.

    In our example code, we have buckets each of ranges from 0 to 1, 1 to 2, 2 to 3,…… (n-1) to n.

    Suppose, an input element is 0.23 is taken. It is multiplied by size = 10 (ie. 0.23*10=2.3 ). Then, it is converted into an integer (ie. 2.3≈2 ). Finally, .23 is inserted into bucket-2.

    Bucket Sort Steps

    Similarly, 0.25 is also inserted into the same bucket. Everytime, the floor value of the floating point number is taken.

    If we take integer numbers as input, we have to divide it by the interval (10 here) to get the floor value.

    Similarly, other elements are inserted into their respective buckets.

    Bucket Sort Steps

  3. The elements of each bucket are sorted using any of the stable sorting algorithms. Here, we have used quicksort (inbuilt function).

    Bucket Sort Steps

  4. The elements from each bucket are gathered.

    It is done by iterating through the bucket and inserting an individual element into the original array in each cycle. The element from the bucket is erased once it is copied into the original array.

    Bucket Sort Steps

Bucket sort is used when:

  • input is uniformly distributed over a range.
  • there are floating point values

Pseudocode

1
2
3
4
5
6
7
8
9
10
bucketSort()
  create N buckets each of which can hold a range of values
  for all the buckets
    initialize each bucket with 0 values
  for all the buckets
    put elements into buckets matching the range
  for all the buckets 
    sort elements in each bucket
  gather elements from each bucket
end bucketSort

Java

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
// Bucket sort in Java

import java.util.ArrayList;
import java.util.Collections;

public class BucketSort {
  public void bucketSort(float[] arr, int n) {
    if (n <= 0)
      return;
    @SuppressWarnings("unchecked")
    ArrayList<Float>[] bucket = new ArrayList[n];

    // Create empty buckets
    for (int i = 0; i < n; i++)
      bucket[i] = new ArrayList<Float>();

    // Add elements into the buckets
    for (int i = 0; i < n; i++) {
      int bucketIndex = (int) arr[i] * n;
      bucket[bucketIndex].add(arr[i]);
    }

    // Sort the elements of each bucket
    for (int i = 0; i < n; i++) {
      Collections.sort((bucket[i]));
    }

    // Get the sorted array
    int index = 0;
    for (int i = 0; i < n; i++) {
      for (int j = 0, size = bucket[i].size(); j < size; j++) {
        arr[index++] = bucket[i].get(j);
      }
    }
  }

  // Driver code
  public static void main(String[] args) {
    BucketSort b = new BucketSort();
    float[] arr = { (float) 0.42, (float) 0.32, (float) 0.33, (float) 0.52, (float) 0.37, (float) 0.47,
        (float) 0.51 };
    b.bucketSort(arr, 7);

    for (float i : arr)
      System.out.print(i + "  ");
  }
}

Radix Sort

  1. Find the largest element in the array, i.e. max. Let X be the number of digits in max. X is calculated because we have to go through all the significant places of all elements.

    In this array [121, 432, 564, 23, 1, 45, 788], we have the largest number 788. It has 3 digits. Therefore, the loop should go up to hundreds place (3 times).

  2. Now, go through each significant place one by one.

    Use any stable sorting technique to sort the digits at each significant place. We have used counting sort for this.

    Sort the elements based on the unit place digits (X=0).

    Radix Sort working with Counting Sort as intermediate step

  3. Now, sort the elements based on digits at tens place.

    Radix Sort Step

  4. Finally, sort the elements based on the digits at hundreds place.

    Selection Sort Step

Pseudocode

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
radixSort(array)
  d <- maximum number of digits in the largest element
  create d buckets of size 0-9
  for i <- 0 to d
    sort the elements according to ith place digits using countingSort

countingSort(array, d)
  max <- find largest element among dth place elements
  initialize count array with all zeros
  for j <- 0 to size
    find the total count of each unique digit in dth place of elements and
    store the count at jth index in count array
  for i <- 1 to max
    find the cumulative sum and store it in count array itself
  for j <- size down to 1
    restore the elements to array
    decrease count of each element restored by 1

Java

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
// Radix Sort in Java Programming

import java.util.Arrays;

class RadixSort {

  // Using counting sort to sort the elements in the basis of significant places
  void countingSort(int array[], int size, int place) {
    int[] output = new int[size + 1];
    int max = array[0];
    for (int i = 1; i < size; i++) {
      if (array[i] > max)
        max = array[i];
    }
    int[] count = new int[max + 1];

    for (int i = 0; i < max; ++i)
      count[i] = 0;

    // Calculate count of elements
    for (int i = 0; i < size; i++)
      count[(array[i] / place) % 10]++;

    // Calculate cumulative count
    for (int i = 1; i < 10; i++)
      count[i] += count[i - 1];

    // Place the elements in sorted order
    for (int i = size - 1; i >= 0; i--) {
      output[count[(array[i] / place) % 10] - 1] = array[i];
      count[(array[i] / place) % 10]--;
    }

    for (int i = 0; i < size; i++)
      array[i] = output[i];
  }

  // Function to get the largest element from an array
  int getMax(int array[], int n) {
    int max = array[0];
    for (int i = 1; i < n; i++)
      if (array[i] > max)
        max = array[i];
    return max;
  }

  // Main function to implement radix sort
  void radixSort(int array[], int size) {
    // Get maximum element
    int max = getMax(array, size);

    // Apply counting sort to sort elements based on place value.
    for (int place = 1; max / place > 0; place *= 10)
      countingSort(array, size, place);
  }

  // Driver code
  public static void main(String args[]) {
    int[] data = { 121, 432, 564, 23, 1, 45, 788 };
    int size = data.length;
    RadixSort rs = new RadixSort();
    rs.radixSort(data, size);
    System.out.println("Sorted Array in Ascending Order: ");
    System.out.println(Arrays.toString(data));
  }
}

 5. Heap Sort

Detailed Working of Heap Sort

To understand heap sort more clearly, let’s take an unsorted array and try to sort it using heap sort.
Consider the array: arr[] = {4, 10, 3, 5, 1}.

Build Complete Binary Tree: Build a complete binary tree from the array.

Build complete binary tree from the array

Build complete binary tree from the array

Transform into max heap: After that, the task is to construct a tree from that unsorted array and try to convert it into max heap.

  • To transform a heap into a max-heap, the parent node should always be greater than or equal to the child nodes
    • Here, in this example, as the parent node 4 is smaller than the child node 10, thus, swap them to build a max-heap.

Transform it into a max heap image widget

  • Now, as seen, 4 as a parent is smaller than the child 5, thus swap both of these again and the resulted heap and array should be like this:

Make the tree a max heap

Make the tree a max heap

Perform heap sort: Remove the maximum element in each step (i.e., move it to the end position and remove that) and then consider the remaining elements and transform it into a max heap.

  • Delete the root element from the max heap. In order to delete this node, try to swap it with the last node, i.e. After removing the root element, again heapify it to convert it into max heap.
    • Resulted heap and array should look like this:

Remove 10 and perform heapify

Remove 10 and perform heapify

  • Repeat the above steps and it will look like the following:

Remove 5 and perform heapify

Remove 5 and perform heapify

  • Now remove the root (i.e. 3) again and perform heapify.

Remove 4 and perform heapify

Remove 4 and perform heapify

  • Now when the root is removed once again it is sorted. and the sorted array will be like arr[] = {1, 3, 4, 5, 10}.

The sorted array

Complexity

Quicksort Complexity

Time Complexity
Best O(n*log n)
Worst O(n2)
Average O(n*log n)
Space Complexity O(log n)
Stability No

  • Worst Case Complexity [Big-O]: O(n2)
    It occurs when the pivot element picked is either the greatest or the smallest element.

    This condition leads to the case in which the pivot element lies in an extreme end of the sorted array. One sub-array is always empty and another sub-array contains n - 1 elements. Thus, quicksort is called only on this sub-array.

    However, the quicksort algorithm has better performance for scattered pivots.

  • Best Case Complexity [Big-omega]: O(n*log n)
    It occurs when the pivot element is always the middle element or near to the middle element.

  • Average Case Complexity [Big-theta]: O(n*log n)
    It occurs when the above conditions do not occur.

Merge Sort Complexity

Time Complexity
Best O(n*log n)
Worst O(n*log n)
Average O(n*log n)
Space Complexity O(n)
Stability Yes

Counting Sort Complexity

Time Complexity
Best O(n+k)
Worst O(n+k)
Average O(n+k)
Space Complexity O(max)
Stability Yes

Time Complexities

There are mainly four main loops. (Finding the greatest value can be done outside the function.)

for-loop time of counting
1st O(max)
2nd O(size)
3rd O(max)
4th O(size)

Overall complexity = O(max)+O(size)+O(max)+O(size) = O(max+size) max -> n, size->k

  • Worst Case Complexity: O(n+k)
  • Best Case Complexity: O(n+k)
  • Average Case Complexity: O(n+k)

In all the above cases, the complexity is the same because no matter how the elements are placed in the array, the algorithm goes through n+k times.

The space complexity of Counting Sort is O(max). Larger the range of elements, larger is the space complexity.

Bucket Sort Complexity

Time Complexity
Best O(n+k)
Worst O(n2)
Average O(n)
Space Complexity O(n+k)
Stability Yes
  • Worst Case Complexity: O(n2)
    When there are elements of close range in the array, they are likely to be placed in the same bucket. This may result in some buckets having more number of elements than others.
    It makes the complexity depend on the sorting algorithm used to sort the elements of the bucket.
    The complexity becomes even worse when the elements are in reverse order. If insertion sort is used to sort elements of the bucket, then the time complexity becomes O(n2).
  • Best Case Complexity: O(n+k)
    It occurs when the elements are uniformly distributed in the buckets with a nearly equal number of elements in each bucket.
    The complexity becomes even better if the elements inside the buckets are already sorted.
    If insertion sort is used to sort elements of a bucket then the overall complexity in the best case will be linear ie. O(n+k). O(n) is the complexity for making the buckets and O(k) is the complexity for sorting the elements of the bucket using algorithms having linear time complexity at the best case.
  • Average Case Complexity: O(n)
    It occurs when the elements are distributed randomly in the array. Even if the elements are not distributed uniformly, bucket sort runs in linear time. It holds true until the sum of the squares of the bucket sizes is linear in the total number of elements.

Radix Sort Complexity

Time Complexity
Best O(n+k)
Worst O(n+k)
Average O(n+k)
Space Complexity O(max)
Stability Yes

Since radix sort is a non-comparative algorithm, it has advantages over comparative sorting algorithms.

For the radix sort that uses counting sort as an intermediate stable sort, the time complexity is O(d(n+k)).

Thus, radix sort has linear time complexity which is better than O(nlog n) of comparative sorting algorithms.

If we take very large digit numbers or the number of other bases like 32-bit and 64-bit numbers then it can perform in linear time however the intermediate sort takes large space.

This makes radix sort space inefficient. This is the reason why this sort is not used in software libraries.

[TOC]