Merge Sort vs. Quick Sort vs. Heap Sort

Read at your own pace. Code execution, quizzes, progress tracking, and the AI tutor are available in the interactive view with JavaScript enabled.

Introduction

In this tutorial, we are going to discuss three O (n log n) sorting techniques, their implementations, and how we derive their runtimes. The learning objectives of this tutorial are as follows:

- You will be able to apply the `Divide-and-Conquer` approach to different sorting methods. - You will be able to sort an array in `O(N log N)` complexity. - We'll learn how to build Max & Min Heaps and apply them to sort an array.

Merge Sort

Merge Sort is a divide and conquer algorithm based on the idea of breaking a list down into several sublists until each sublist contains only a single item. Afterwards, we will merge these sublists in such a manner that the resulting list will be sorted.

Essential Idea

Divide the list into sub-lists, each containing a single element.

Merge adjacent pairs of two "singleton" (containing only one element) lists to form a list of 2 elements.

Repeat the above steps, until we get a fully sorted list.

Let's consider an example to understand this approach better.

Array Example

We have an array containing eight elements and two pointers directed at the first and last element.

Dividing the array

One can understand from the images below that at each step, the array of size M is divided into two sublists, of size M/2, until no further division is possible.

Partition_1 Partition_2

We divide the array using the function merge_sort(array, startIndex, lastIndex). As shown in the images above, merge_sort recursively divided the array into halves until we reach the base case where each subarray contains only single element.

Merging the sub-arrays

After dividing the array, we will call the merge function that picks up the sorted sub-arrays and combines them to gradually sort the array. This function will also merge the sub-arrays recursively in such a way that a fully sorted array can be obtained.

The below images demonstrates the merging of an array in action.

Merging_1

Merging_2

Implementation Of MergeSort

The merge sort can be implemented using the two functions described below.

merge_sort(array, startIndex, lastIndex)

merge(array, startIndex, middle, lastIndex)

Here, in the merge function, we will merge two sub-arrays. One sub-array has a range from start to middlewhile the other will go from middle+1 to the last index. We will divide the array into sub-arrays on the merge_sort function.

An implementation of the MergeSort algorithm has been provided below:

```cpp
#include<stdlib.h> 
#include<stdio.h> 
#include<iostream>

using namespace std;

const int Size = 8;

void merge(int Array[], int Firstindex, int m, int Lastindex); //this function will merge all the sub-arrays 

void merge_sort(int Array[], int Firstindex, int Lastindex)
{
    if (Firstindex < Lastindex)
    {

        int m = Firstindex + (Lastindex - Firstindex) / 2;


        merge_sort(Array, Firstindex, m);
        merge_sort(Array, m + 1, Lastindex);

        merge(Array, Firstindex, m, Lastindex);
    }
}

void merge(int Array[], int Firstindex, int m, int Lastindex)
{
    int x,y,z;
  
    int subArray1 = m - Firstindex + 1;
    int subArray2 = Lastindex - m;


    int *First = new int[subArray1];  //auxiliary array

    int *Second= new int[subArray2];


    for (x = 0; x < subArray1; x++) // duplicating data to auxiliary array
        First[x] = Array[Firstindex + x];
    for (y = 0; y < subArray2; y++)
        Second[y] = Array[m + 1 + y];


    x = 0;
    y = 0;
    z = Firstindex;
    while (x < subArray1 && y < subArray2)
    {
        if (First[x] <= Second[y])
        {
            Array[z] = First[x];
            x++;
        }
        else
        {
            Array[z] = Second[y];
            y++;
        }
        z++;
    }
    while (x < subArray1)
    {
        Array[z] = First[x];
        x++;
        z++;
    }
    while (y < subArray2)
    {
        Array[z] = Second[y];
        y++;
        z++;
    }
}
int main()
{
   
    int Array[Size] = { 2,8,5,3,9,4,1,7 };
    
    merge_sort(Array, 0, Size - 1);
    cout << "The Sorted array is : " << endl;
    for (int i = 0; i < Size; i++)
    {
        cout << Array[i] << " ";
    }
    return 0;
}
```    
```csharp
using System;

public class Program
{
    public static void MergeSort(int[] array, int firstindex, int lastindex)
    {
        if (firstindex < lastindex)
        {
            int m = firstindex + (lastindex - firstindex) / 2;

            MergeSort(array, firstindex, m);
            MergeSort(array, m + 1, lastindex);

            Merge(array, firstindex, m, lastindex);
        }
    }

    public static void Merge(int[] array, int firstindex, int m, int lastindex)
    {
        int x, y, z;

        int subArray1 = m - firstindex + 1;
        int subArray2 = lastindex - m;

        int[] First = new int[subArray1];

        int[] Second = new int[subArray2];


        for (x = 0; x < subArray1; x++)
            First[x] = array[firstindex + x];
        for (y = 0; y < subArray2; y++)
            Second[y] = array[m + 1 + y];

        x = 0;
        y = 0;
        z = firstindex;
        while (x < subArray1 && y < subArray2)
        {
            if (First[x] <= Second[y])
            {
                array[z] = First[x];
                x++;
            }
            else
            {
                array[z] = Second[y];
                y++;
            }
            z++;
        }
        while (x < subArray1)
        {
            array[z] = First[x];
            x++;
            z++;
        }
        while (y < subArray2)
        {
            array[z] = Second[y];
            y++;
            z++;
        }
    }

    public static void Main(string[] args)
    {
        const int size = 8;

        int[] array = { 2, 8, 5, 3, 9, 4, 1, 7 };

        MergeSort(array, 0, size - 1);

        Console.WriteLine("The Sorted array is : ");

        for (int i = 0; i < size; i++)
        {
            Console.Write(array[i] + " ");
        }
    }
}
```
```java
public class Main{

    public static void mergeSort(int[] array, int firstindex, int lastindex) {
        if (firstindex < lastindex) {
            int m = firstindex + (lastindex - firstindex) / 2;

            mergeSort(array, firstindex, m);
            mergeSort(array, m + 1, lastindex);

            merge(array, firstindex, m, lastindex);
        }
    }

    public static void merge(int[] array, int firstindex, int m, int lastindex) {
        int x, y, z;

        int subArray1 = m - firstindex + 1;
        int subArray2 = lastindex - m;

        int[] First = new int[subArray1];

        int[] Second = new int[subArray2];

        for (x = 0; x < subArray1; x++) {
            First[x] = array[firstindex + x];
        }
        for (y = 0; y < subArray2; y++) {
            Second[y] = array[m + 1 + y];
        }

        x = 0;
        y = 0;
        z = firstindex;
        while (x < subArray1 && y < subArray2) {
            if (First[x] <= Second[y]) {
                array[z] = First[x];
                x++;
            } else {
                array[z] = Second[y];
                y++;
            }
            z++;
        }
        while (x < subArray1) {
            array[z] = First[x];
            x++;
            z++;
        }
        while (y < subArray2) {
            array[z] = Second[y];
            y++;
            z++;
        }
    }

    public static void main(String[] args) {
        int size = 8;
        int[] array = {2, 8, 5, 3, 9, 4, 1, 7};

        mergeSort(array, 0, size - 1);

        System.out.println("The Sorted array is : ");

        for (int i = 0; i < size; i++) {
            System.out.print(array[i] + " ");
        }
    }
}
```
```js
function merge(leftArr, rightArr) {
  let resultArray = [], leftIndex = 0, rightIndex = 0;

  // Sort parts
  while (leftIndex < leftArr.length && rightIndex < rightArr.length) {
    if (leftArr[leftIndex] < rightArr[rightIndex]) {
      resultArray.push(leftArr[leftIndex]);
      leftIndex++; // move left array cursor
    } else {
      resultArray.push(rightArr[rightIndex]);
      rightIndex++; // move right array cursor
    }
  }

  // There will be one element remaining from either left or the right
  // Concat to account for it
  return resultArray
          .concat(leftArr.slice(leftIndex))
          .concat(rightArr.slice(rightIndex));
}

function mergeSort(unsortedArr) {
  // Only one element base case
  if (unsortedArr.length <= 1) {
    return unsortedArr;
  }

  // Determine midpoint
  const midIdx = Math.floor(unsortedArr.length / 2);

  // Divide the array into left and right
  const leftArr = unsortedArr.slice(0, midIdx);
  const rightArr = unsortedArr.slice(midIdx);

  // Recursively merge
  return merge(
    mergeSort(leftArr), mergeSort(rightArr)
  );
}

console.log(mergeSort([5, 4, 3, 2, 1]));
```
```py
def merge(a, b, c=[]):
    if len(a) == 0:
        return c + b
    elif len(b) == 0:
        return c + a
    else:
        a_first = a[0]
        b_first = b[0]
        if a_first <= b_first:
            return merge(a[1:], b, c + [a_first])
        else:
            return merge(a, b[1:], c + [b_first])

def merge_sort(arr):
    length = len(arr)
    if length < 2:
        return arr
    else:
        mid = length // 2   
        return merge(merge_sort(arr[0:mid]), merge_sort(arr[mid:]))

print(merge_sort([5, 4, 3, 2, 1]));
```

Time Complexity Of MergeSort

Time Complexity

The merging of all the sub-arrays into a single array will take O(N) time, while the array of size N can be divided into logN parts, hence the worst case of merge sort is O(N log N).

Question 1

The worst-case scenario time complexity of the MergeSort algorithm is:

Quick Sort

The quicksort algorithm is based on the divide and conquer technique. We start by:

Choosing one element as a pivot, and
Divide the array around it, such that all the elements on the left of the pivot are smaller than the it, and all the elements on the right are greater than the pivot.

How does Quick Sort work?

We will choose a random element from the array as a pivot and swap it with the last element of the array. We will also initialize two pointers left and right pointing to the start and end of the array.

Following this setup, we will rearrange the elements in such a way that the left side of the pivot contains elements that are the smaller and right side of the pivot contains elements that are greater than the pivot. We can accomplish this by following the steps below.

Move the left pointer to the right until it reaches a value greater or equal to the pivot. Afterward, stop the left pointer and move to step 2.

Move the right pointer to the left until it crosses the left pointer or finds a value less than the pivot.

Repeat the above steps until unless both pointers cross each other.

Let's take a look at the following illustrations to understand the approach better. In the figure below, we have chosen the pivot and swapped it with the last element of the array.

Choosing Pivot

Now, we move the left and right pointer depending on the steps described above. If right < left, then we will swap them.

Pivot_1

Now, we can see in the figure below that both pointers crossed each other. Given this, we will mark the element pointed by the left pointer as sorted.

Pointer Crossed

We will then repeat the above steps by first choosing the pivot and swapping it with the last index and so on. At last, we will have all elements sorted.

Sorted Array

Implementation of Quick Sort

Quick Sort can be implemented using two functions described below:

partition(Array, startIndex, lastIndex)

quick_sort(Array, startIndex, lastIndex)

Here, in the partition function, we are dividing the array based upon the selected pivot. In the quick_sort function, we are re-arranging the elements.

```py
def partition(arr, low, high):
    low_idx = low - 1
    pivot = arr[high]  # pivot

    for j in range(low, high):
        # If current element is smaller than or
        # equal to pivot
        if arr[j] <= pivot:
            # Increment index of left/smaller element
            low_idx = low_idx + 1
            # Swap
            arr[low_idx], arr[j] = arr[j], arr[low_idx]

    arr[low_idx + 1], arr[high] = arr[high], arr[low_idx + 1]
    return low_idx + 1


def quick_sort(arr, low, high):
    if len(arr) == 1:
        # Base case
        return arr
    if low < high:
        partition_idx = partition(arr, low, high)

        # Recursively sort elements before partition
        # and after partition
        quick_sort(arr, low, partition_idx - 1)
        quick_sort(arr, partition_idx + 1, high)

    return arr

nums = [10, 50, 6, 33, 2, 2, 50]
print(quick_sort(nums, 0, len(nums) - 1))
```
```js
function partition(arr, low, high) {
    let lowIdx = low - 1;
    let pivot = arr[high];  // pivot

    for (let j = low; j < high; j++) {
        // If current element is smaller than or
        // equal to pivot
        if (arr[j] <= pivot) {
            // Increment index of left/smaller element
            lowIdx = lowIdx + 1;
            // Swap
            const temp = arr[lowIdx];
            arr[lowIdx] = arr[j];
            arr[j] = temp;
        }
    }

    const temp = arr[lowIdx + 1];
    arr[lowIdx + 1] = arr[high];
    arr[high] = temp;

    return lowIdx + 1
}

function quickSort(arr, low, high) {
    if (arr.length === 1) {
        // Base case
        return arr;
    }
    
    if (low < high) {
        partitionIdx = partition(arr, low, high)

        // Recursively sort elements before partition
        // and after partition
        quickSort(arr, low, partitionIdx - 1)
        quickSort(arr, partitionIdx + 1, high)
    }

    return arr
}

const nums = [10, 50, 6, 33, 2, 2, 50];
console.log(quickSort(nums, 0, nums.length - 1))
```
```cpp
#include <iostream>
#include <algorithm>
using namespace std;

int partition(int Array[], int startIndex, int lastIndex)
{
    // choosing the last element as pivot
    int pivot = Array[lastIndex];

    // Push the elements to the left of pointer that are smaller than pivot
    // Push the elements to the right of pointer that are greater than pivot
    // equal elements can go either way
    int pointer = startIndex;

    // each time we finds an element less than or equal to pivot, pointer
    // is incremented and that element would be placed before the pivot.
    for (int i = startIndex; i < lastIndex; i++)
    {
        if (Array[i] <= pivot)
        {
            swap(Array[i], Array[pointer]);
            pointer++;
        }
    }
    // swap pointer with Pivot
    swap(Array[pointer], Array[lastIndex]);

    // returning the index of the pivot
    return pointer;
}


void quick_sort(int Array[], int startIndex, int lastIndex)
{
    // base condition
    if (startIndex >= lastIndex)
        return;

    // again calling partion function to rearrange elements around the pivot
    int pivot = partition(Array, startIndex, lastIndex);

    // this will contains the element that are less than pivot
    quick_sort(Array, startIndex, pivot - 1);

    // this will contains the element that are greater than pivot
    quick_sort(Array, pivot + 1, lastIndex);
}

// Driver Code
int main()
{
    int Array[] = { 10,50,6,33,2 };
    int n = sizeof(Array) / sizeof(Array[0]);

    quick_sort(Array, 0, n - 1);

    // we are printing the sorted array
    for (int i = 0; i < n; i++)
        cout << Array[i] << " ";

    return 0;
}
```
```csharp
using System;

public class Program
{
    public static int Partition(int[] array, int startIndex, int lastIndex)
    {
        // choosing the last element as pivot
        int pivot = array[lastIndex];
        int temp;

        // Push the elements to the left of pointer that are smaller than pivot
        // Push the elements to the right of pointer that are greater than pivot
        // equal elements can go either way
        int pointer = startIndex;

        // each time we finds an element less than or equal to pivot, pointer
        // is incremented and that element would be placed before the pivot.
        for (int i = startIndex; i < lastIndex; i++)
        {
            if (array[i] <= pivot)
            {
                temp = array[i];
                array[i] = array[pointer];
                array[pointer] = temp;
                pointer++;
            }
        }

        // swap pointer with Pivot
        temp = array[pointer];
        array[pointer] = array[lastIndex];
        array[lastIndex] = temp;

        // returning the index of the pivot
        return pointer;
    }


    public static void QuickSort(int[] array, int startIndex, int lastIndex)
    {
        // base condition
        if (startIndex >= lastIndex)
            return;

        // again calling partion function to rearrange elements around the pivot
        int pivot = Partition(array, startIndex, lastIndex);

        // this will contains the element that are less than pivot
        QuickSort(array, startIndex, pivot - 1);

        // this will contains the element that are greater than pivot
        QuickSort(array, pivot + 1, lastIndex);
    }

    public static void Main(string[] args)
    {
        int[] array = { 10, 50, 6, 33, 2 };
        int n = array.Length;

        QuickSort(array, 0, n - 1);

        // we are printing the sorted array
        for (int i = 0; i < n; i++)
            Console.Write(array[i] + " ");
    }
}
```
```java

public class Main {

    public static int Partition(int[] array, int startIndex, int lastIndex) {
        // choosing the last element as pivot
        int pivot = array[lastIndex];
        int temp;

        // Push the elements to the left of pointer that are smaller than pivot
        // Push the elements to the right of pointer that are greater than pivot
        // equal elements can go either way
        int pointer = startIndex;

        // each time we finds an element less than or equal to pivot, pointer
        // is incremented and that element would be placed before the pivot.
        for (int i = startIndex; i < lastIndex; i++) {
            if (array[i] <= pivot) {
                temp = array[i];
                array[i] = array[pointer];
                array[pointer] = temp;
                pointer++;
            }
        }

        // swap pointer with Pivot
        temp = array[pointer];
        array[pointer] = array[lastIndex];
        array[lastIndex] = temp;

        // returning the index of the pivot
        return pointer;
    }

    public static void QuickSort(int[] array, int startIndex, int lastIndex) {
        // base condition
        if (startIndex >= lastIndex) {
            return;
        }

        // again calling partion function to rearrange elements around the pivot
        int pivot = Partition(array, startIndex, lastIndex);

        // this will contains the element that are less than pivot
        QuickSort(array, startIndex, pivot - 1);

        // this will contains the element that are greater than pivot
        QuickSort(array, pivot + 1, lastIndex);
    }

    public static void main(String[] args) {
        int[] array = {10, 50, 6, 33, 2};
        int n = array.length;

        QuickSort(array, 0, n - 1);

        // we are printing the sorted array
        for (int i = 0; i < n; i++) {
            System.out.print(array[i] + " ");
        }
    }
}

```

Comparison with MergeSort

Comparison with Merge Sort

With quick sort, there is no need to use the auxiliary array that we used in the merge sort approach. This reduces the space complexity and choosing a random pivot from array improves the time complexity as well.

Question 2

Choose a random element from the array as a pivot and swap pivot with the last element of the array. Initialize two pointers left and right pointing to the start and end of the array.

This principle is implemented in which type of sorting algorithm?

Heap Sort

Finally, heap sort is based on comparisons. We can say that it is an improved version of selection sort. It actually visualizes the array elements as heap.

Heap

A heap is a tree-based structure. The definition of one is that it is a complete binary tree and all the nodes are greater than their children. A heap is said to be a Min-Heap if all the nodes are smaller than their children, otherwise it will be considered as a Max-Heap.

How to heapify a tree?

A function called heapify can be used on all non-leaf nodes of the heap in order to make a Max-Heap.

Implementation of HeapSort

Consider an Array which is to be sorted using heap sort. To begin, we will create Max-Heap using the elements of Array.

Heap_1

The first element of the array would be the largest, so we will swap this element with the last one. We will heapify the Max-Heap but exclude the last element as it is already in its correct position. After that, we will decrease the length of the array by one. Then, we will repeat this step until all the elements in the array are in their correct position.

The following steps should be taken in order to sort the above Array.

Step 1: 8 is swapped with 5.
Step 2: 8 is disconnected from the heap as 8 is in the correct position now and.
Step 3: Max-heap is created and 7 is swapped with 3.
Step 4: 7 is disconnected from the heap.
Step 5: Max heap is created and 5 is swapped with 1.
Step 6: 5 is disconnected from the heap.
Step 7: Max heap is created and 4 is swapped with 3.
Step 8: 4 is disconnected from the heap.
Step 9: Max heap is created and 3 is swapped with 1.
Step 10: 3 is disconnected

The following illustrations will demonstrate the above steps.

Heap_2

Heap_3

After all the steps, we will get the sorted array.

Heap_4

Implementation of Heap Sort

In C++, the following functions will be used to implement Heap Sort.

heapify(Array, size, index)

heapSort(Array, size)

The heapify function will convert all non-leaf nodes of the heap to Max-Heap and heapSort will first create a priority queue, and then repeatedly pop the elements from the heap until it becomes empty. Implementation of HeapSort has been provided below:

```py
def heapify(arr, start, end):
    parent = start
    child = parent * 2 + 1

    while child <= end:
        if child + 1 <= end and arr[child] < arr[child + 1]:
            child += 1

        if arr[parent] >= arr[child]:
            break
        else:
            arr[parent], arr[child] = arr[child], arr[parent]
            parent = child
            child = parent * 2 + 1


def heap_sort(arr):
    length = len(arr)

    for i in range(length // 2 - 1, -1, -1):
        heapify(arr, i, length - 1)

    for i in range(length - 1, -1, -1):
        arr[0], arr[i] = arr[i], arr[0]
        heapify(arr, 0, i - 1)


if __name__ == '__main__':
    arr = [4, 11, 1, 21, 34, 85, 6, 49, 7, 12, 31]
    heap_sort(arr)
    print(arr)
```
```js
const heapSort = function(arr) {
  const n = arr.length;
  for (let i = Math.floor(n/2) - 1; i >= 0; i--) {
    heapify(arr, n, i);
  }

  for (let i = n - 1; i >= 0; i--) {
    swap(arr, 0, i);
    heapify(arr, i, 0);
  }

  return arr;
}

const heapify = function(arr, n, i) {
  // find places in array heap
  let left = 2 * i + 1;
  let right = 2 * i + 2;

  if (left >= n && right >= n) { return; }

  const leftValue = (left >= n) ? Number.NEGATIVE_INFINITY : arr[left];
  const rightValue = (right >= n) ? Number.NEGATIVE_INFINITY : arr[right];

  if (arr[i] > leftValue && arr[i] > rightValue) { return; }

  if (leftValue > rightValue) {
    swap(arr, i, left);
    heapify(arr, n, left);
  } else {
    swap(arr, i, right);
    heapify(arr, n, right);
  }
}

function swap(arr, a, b) {
  const temp = arr[a];
  arr[a] = arr[b];
  arr[b] = temp;
}

console.log(heapSort([4, 11, 1, 21, 34, 85, 6, 49, 7, 12, 31]));
```
```cpp
#include <iostream>
#include <vector>
using namespace std;

// We are using Priority Queues for Max-Heap
class PriorityQueue
{
    // for the left chide of Array[i]
    int leftChild(int i) {
        return (2 * i + 1);
    }

    // for the right child of Array[i]
    int rightChild(int i) {
        return (2 * i + 2);
    }

    //this function implements the recursive Heapify-down algorithm
    void Heapify(vector<int>& Array, int i, int size)
    {
        // we are storing the left and right child nodes
        int left = leftChild(i);
        int right = rightChild(i);

        int maxvalue = i;

        
        //finding the max value by comparing with the left and child node of A[i]
        if (left < size && Array[left] > Array[i]) {
            maxvalue = left;
        }

        if (right < size && Array[right] > Array[maxvalue]) {
            maxvalue = right;
        }

       
        //we are swaping the max value and then calling the heapify-down on the child
        if (maxvalue != i) {
            swap(Array[i], Array[maxvalue]);
            Heapify(Array, maxvalue, size);
        }
    }

public:

    // Constructor 
    PriorityQueue(vector<int>& A, int n)
    {
        
        //calling Heapify function starting from the last node all the way to the root node.
        int i = (n - 2) / 2;
        while (i >= 0) {
            Heapify(A, i--, n);
        }
    }

    //removing highest priority elements
    int pop(vector<int>& Array, int size)
    {
        // if empty Heap
        if (size <= 0) {
            return -1;
        }

        int top = Array[0];

        
        Array[0] = Array[size - 1];

        // call heapify-down on root node
        Heapify(Array, 0, size - 1);

        return top;
    }
};


void HeapSort(vector<int>& Array, int n)
{
    
    PriorityQueue temp(Array, n);

    
    while (n > 0) {
        Array[n - 1] = temp.pop(Array, n);
        n--;
    }
}

// Driver Code
int main()
{
    vector<int> Array = {4,3,7,1,8,5 };
    int n = Array.size();

    
    HeapSort(Array, n);

    // we are printing the sorted array
    cout << "The sorted array is : " << endl;
    for (int i = 0; i < n; ++i) {
        cout << Array[i] << " ";
    }

    return 0;
}
```
```csharp
using System;

public class Program
{
    // We are using Priority Queues for Max-Heap
    public class PriorityQueue
    {
        // for the left chide of Array[i]
        public int LeftChild(int i)
        {
            return (2 * i + 1);
        }

        // for the right child of Array[i]
        public int RightChild(int i)
        {
            return (2 * i + 2);
        }

        //this function implements the recursive Heapify-down algorithm
        public void Heapify(int[] array, int i, int size)
        {
            // we are storing the left and right child nodes
            int left = LeftChild(i);
            int right = RightChild(i);

            int maxvalue = i;
            int tempInt;

            //finding the max value by comparing with the left and child node of A[i]
            if (left < size && array[left] > array[i])
            {
                maxvalue = left;
            }

            if (right < size && array[right] > array[maxvalue])
            {
                maxvalue = right;
            }

            //we are swaping the max value and then calling the heapify-down on the child
            if (maxvalue != i)
            {
                tempInt = array[i];
                array[i] = array[maxvalue];
                array[maxvalue] = tempInt;
                Heapify(array, maxvalue, size);
            }
        }


        // Constructor 
        public PriorityQueue(int[] A, int n)
        {

            //calling Heapify function starting from the last node all the way to the root node.
            int i = (n - 2) / 2;
            while (i >= 0)
            {
                Heapify(A, i--, n);
            }
        }

        //removing highest priority elements
        public int Pop(int[] Array, int size)
        {
            // if empty Heap
            if (size <= 0)
            {
                return -1;
            }

            int top = Array[0];


            Array[0] = Array[size - 1];

            // call heapify-down on root node
            Heapify(Array, 0, size - 1);

            return top;
        }
    };


    public static void HeapSort(int[] array, int n)
    {
        PriorityQueue temp = new PriorityQueue(array, n);

        while (n > 0)
        {
            array[n - 1] = temp.Pop(array, n);
            n--;
        }
    }

    public static void Main(string[] args)
    {
        int[] array = { 4, 3, 7, 1, 8, 5 };
        int n = array.Length;

        HeapSort(array, n);

        // we are printing the sorted array
        Console.WriteLine("The sorted array is : ");
        for (int i = 0; i < n; ++i)
        {
            Console.Write(array[i] + " ");
        }
    }
}
```
```java

public class Main {

  static class PriorityQueue {

        // for the left chide of Array[i]
        public int LeftChild(int i) {
            return (2 * i + 1);
        }

        // for the right child of Array[i]
        public int RightChild(int i) {
            return (2 * i + 2);
        }

        //this function implements the recursive Heapify-down algorithm
        public void Heapify(int[] array, int i, int size) {
            // we are storing the left and right child nodes
            int left = LeftChild(i);
            int right = RightChild(i);

            int maxvalue = i;
            int tempInt;

            //finding the max value by comparing with the left and child node of A[i]
            if (left < size && array[left] > array[i]) {
                maxvalue = left;
            }

            if (right < size && array[right] > array[maxvalue]) {
                maxvalue = right;
            }

            //we are swaping the max value and then calling the heapify-down on the child
            if (maxvalue != i) {
                tempInt = array[i];
                array[i] = array[maxvalue];
                array[maxvalue] = tempInt;
                Heapify(array, maxvalue, size);
            }
        }

        // Constructor 
        public PriorityQueue(int[] A, int n) {

            //calling Heapify function starting from the last node all the way to the root node.
            int i = (n - 2) / 2;
            while (i >= 0) {
                Heapify(A, i--, n);
            }
        }

        //removing highest priority elements
        public int Pop(int[] Array, int size) {
            // if empty Heap
            if (size <= 0) {
                return -1;
            }

            int top = Array[0];

            Array[0] = Array[size - 1];

            // call heapify-down on root node
            Heapify(Array, 0, size - 1);

            return top;
        }
    };

    public static void HeapSort(int[] array, int n) {
        PriorityQueue temp = new PriorityQueue(array, n);

        while (n > 0) {
            array[n - 1] = temp.Pop(array, n);
            n--;
        }
    }

    public static void main(String[] args) {
        int[] array = {4, 3, 7, 1, 8, 5};
        int n = array.length;

        HeapSort(array, n);

        // we are printing the sorted array
        System.out.println("The sorted array is : ");
        for (int i = 0; i < n; ++i) {
            System.out.print(array[i] + " ");
        }
    }
}

```

Question 3

A function called heapify can be used on all nodes of the heap in order to make a Max-Heap, no matter the node types.

Complexity of HeapSort

Heap sort has the time complexity of O(N log N) for all cases.

Note that heap sort is not stable. Stable sorting allows us to sort based on more than one key. Operations in the heap can change the relative order of equivalent keys-- picture the event of two identical numbers in the heap, which make their way to different locations.

Question 4

Which of the following sorting algorithms is based on the divide-and-conquer principle?

One Pager Cheat Sheet

We will learn how to use the Divide-and-Conquer approach and apply it to sort an array in O(N log N) complexity using Max & Min Heaps.
Merge Sort is an efficient divide and conquer algorithm that breaks down lists into smaller sublists, sorts them, and then merges them in order to create a fully sorted list.
The MergeSort algorithm can be implemented using two functions - merge_sort(array, startIndex, lastIndex) and merge(array, startIndex, middle, lastIndex), which divides and merges sub-arrays.
The sorting of an array of size N using Merge Sort has a worst-case time complexity of O(N log N).
The worst-case time complexity of MergeSort is O(N logN), resulting from the merging of N elements and the splitting of each element into logN parts.
The Quick Sort algorithm is based on the divide and conquer technique, whereby a pivot element is chosen, and the array is divided into two sides, with elements on the left being smaller than the pivot, and elements on the right being greater.
Quick Sort can be implemented using two functions, partition and quick_sort, to divide and re-arrange elements in the array based on a selected pivot.
Quick sort reduces the space complexity and improves the time complexity by using an random pivot selection from the array, compared to merge sort.
Quick Sort uses a partitioning process to split the unsorted array around a randomly chosen pivot element and recursively sort the subarrays.
Heap Sort is an improved version of selection sort which views the Array as a Max-Heap and utilizes a heapify function to put the elements in their correct positions.
The heapify and heapSort functions are used to implement Heap Sort in C++.
The heapify function can only be used on non-leaf nodes to convert them to a Max-Heap, as leaf nodes have no children to be converted.
Heap sort has a time complexity of O(N log N), but is not stable.
Both Merge Sort and Quick Sort are popular sorting algorithms based on the divide-and-conquer principle, where a problem is broken down into smaller sub-problems and then combined to get the desired result.

Open interactive view →