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:

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

1. Divide the list into sub-lists, each containing a single element.
2. Merge adjacent pairs of two "singleton" (containing only one element) lists to form a list of 2 elements.
3. Repeat the above steps, until we get a fully sorted list.

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

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.

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.

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

Quick Sort

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

1. Choosing one element as a pivot, and
2. 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.

1. 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.
2. Move the right pointer to the left until it crosses the left pointer or finds a value less than the pivot.
3. 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.

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

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.

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.

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.

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.

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.

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

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.

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.