Advanced Sorting Algorithms - DSA #6

In this note, we will discover three super efficient sorting algorithms: Heap Sort, Quick Sort, and Merge Sort!

Efficient Sorting Algorithms

The elementary sorting algorithms discussed in my previous note, Basic Sorting Algorithms - DSA #5, are of the order $\Theta(n^2)$, which is pretty inefficient especially for large datasets.

There are more efficient sorting algorithms that are of the order $\mathcal{O}(n\log n)$, and three typical algorithms are Heap Sort, Quick Sort, and Merge Sort.

Heap Sort

Heap Sort was invented by J. W. J. Williams in 1964. This was also the birth of the heap, presented already by Williams as a useful data structure.

The idea of Heap Sort comes from the method of sorting by the Selection Sort — repeatedly choosing the least key (or the smallest item) and move it to the start/end of the array. How can this idea possibly be improved?

Basic Concept of Heap Sort

The First Stage

Traditional Selection Sort finds the smallest element in each pass using $n−1$ comparisons. This process discards useful information, as it only identifies a single least item per scan. Instead of merely identifying the smallest element in each pass, comparisons can be structured hierarchically:

• Compare items in pairs, requiring $\frac{n}{2}$ comparisons to find the smaller of each pair.
• Compare the smaller values from the previous step, using $\frac{n}{4}$ comparisons.
• This continues recursively, reducing the number of comparisons at each level.

Suppose we have the array $8, 3, 6, 2, 5, 9, 4, 1$. We compare in pairs:$(8, 3) \Rightarrow 3$, $(6, 2) \Rightarrow 2$, $(5, 9) \Rightarrow 5$, $(4, 1) \Rightarrow 1$. The total comparisons of this round is $8 / 2 = 4$.

After the first round, we are left with $\frac{n}{2}$ elements. In the second round, we again compare them in pairs, needing $\frac{n}{4}$ comparisons. The process continues until one element remains.

With $n - 1$ comparisons, we can build a selection tree, and identify the root as the desired least key. This is the idea of the heap data structure.

Let’s construct a heap from the above example array:

Compare the elements in pairs of the array to select the smaller element of each pair:

The number of comparisons in this round is $\frac{n}{2} = 4$.

In the next round, continue comparing the remaining elements in pairs:

The number of comparisons in this round is $\frac{\frac{n}{2}}{2} = \frac{n}{4} = 2$.

Identify the desired least key:

The number of comparisons in this round is $\frac{\frac{n}{4}}{2} = \frac{n}{8} = 1$. The above is a simple heap data structure from the given integers.

The Second Stage

The following steps will be repeated until the heap is full of the key $∞$:

• Extract the least key at the root and replace it by an empty hole.
• Descend down along the path marked by the least key and replace it by an empty hole.
• Fill the empty hole at the bottom with $∞$ and ascend up along the path marked by empty holes, filling them with $∞$ or the key at the alternative branch.

Each of the above repetitions is called a selection step.

Let’s get back to the heap we’ve constructed in the previous step:

Let’s use this to visualize how this would work ($\square$ as empty holes):

From the illustration, we can see that the algorithm repeatedly select the root key, and they’re actually picked up in the correct order: $1 → 2 → 3 → 4 → 5 → 6 → 8 → 9$! Isn’t that cool?

Remarks

Without a doubt, after $n$ selection steps, the tree is full of $∞$, and the sorting process is terminated. Each of the $n$ selection steps requires $\log_2{n}$ comparisons; thus, the second stage requires a linearithmic running time.

However, this approach has several weaknesses:

• The heap requires $2n - 1$ units of storage to store $n$ items.
• The occurrences of $∞$ in the heap are the source of many unnecessary comparisons.
• Most importantly, it is easier said than done, as it is too difficult for computers to simulate!

An Ingenious Idea

Heap Definition

From the above drawbacks, clearly, we need to find a way to store the structure using $n$ units of storage instead of $2n - 1$. From this, the author of Heap Sort proposes a super cool idea:

A heap is a sequence of elements $h_1, h_2, \dots, h_n$ such that:

$h_i ≤ h_{2i} \\ h_i ≤ h_{2i + 1}$

for all $i = 1, 2, \dots, \lfloor \frac{n}{2} \rfloor$.

The sequence of elements $h_{\lfloor \frac{n}{2} \rfloor + 1}, \dots, h_n$ is a natural heap, and the element $h_1$ of a heap is its least value.

This is an example heap:

where $[9 \quad 6 \quad 4 \quad 8]$ is a natural heap.

Let’s arrange this sequence of elements into a pictorial representation of a heap:

Finally, a heap can be stored using $n$ units of storage!

Heap Construction

How can we reconstruct a heap if the element at the root is not the smallest key? The solution is as follows:

• A new heap is obtained by letting the element on top of the subheap “sift down” along the path of the smaller comparand, which at the same time move up.
• The “sift down” process stops when the element on top of the subheap is smaller than or equal to both its comparands.

Let’s visualize the process with this tree:

We choose the subheap containing the elements $10, 15, 50$. Sift $15$ down to the smaller comparand $10$, and move $10$ up towards the position of $15$.

There’s actually another subheap to take into account. We will now choose the subheap of $40, 50, 70$. Sift $50$ down to $40$, and move $40$ up towards the position of $50$.

After the sifting process, we now have a valid heap!

The Sifting Algorithm

As mentioned above, given an array of $n$ integers $a_1, a_2, … a_n$, the sequence of elements $a_{\lfloor\frac{n}{2}\rfloor + 1}, … a_n$ is a natural heap.

Starting from the natural heap, we extend it to the left where in each step a new element is included and properly positioned by a sift.

left = n / 2;

while (left > 0) {
	sift(a, left, n);
	left--;
}

Here is how we would implement the sifting algorithm:

sift(a[], left, right) {
	i = left; j = 2 * i;
	x = a[i]; 
	// Extract the least key
	// We need to store the key to another variable, x
	
	while (j ≤ right) {
		// j < right: Check if a[i] 
		// has one or two comparands
		if (j < right)
			// a[j] > a[j + 1]: Make sure that a[j] is
			// always the smaller among the 2 comparands
			if (a[j] > a[j + 1]) j++;
		if (x ≤ a[j]) break;
		a[i] = a[j];      // "sift down" along the path
		i = j; j = 2 * i; // of the smaller comparand
	}
	a[i] = x;
}

Let’s simulate this with an example array (the natural heap is marked as $\lfloor --- \rfloor$):

Let’s start with $left = \frac{n}{2} = 4$, $i = left = 4$, $j = i * 2 = 8$. The value of $right$ is always $n = 9$ throughout the process.

$a[j]$ is already smaller compared to $a[j + 1]$. Since $a[i] = 8$ is larger than $a[j] = 1$, these two elements will be swapped. Then we will update $i = j = 8$ and $j = i * 2 = 16$. Since $j > right$, there’s no need for another sifting!

We only want the smaller between $a[j]$ and $a[j - 1]$, so $j$ is incremented by $1$ to get the index of that smaller element.

$a[i] = 5 > a[j] = 3$ so $a[i] ⇄ a[j]$. Then, $i = j = 7, j = i * 2 = 14 > right$ so this stage is done.

$a[i] = 9 > a[j] = 1$ so $a[i] ⇄ a[j]$. Then, $i = j = 4, j = i * 2 = 8 < right$. We need to do another sifting.

We increment $j$ to $9$ to get the smaller element. $a[i] = 9 > a[j] = 5$ so $a[i] ⇄ a[j]$. Then, $i = j = 9, j = i * 2 = 18 > right$ so this stage is done.

$a[i] = 7 > a[j] = 1$ so $a[i] ⇄ a[j]$. Then, $i = j = 2, j = i * 2 = 4 < right$. We need to do another sifting.

We increment $j$ to $5$ to get the smaller element. $a[i] = 7 > a[j] = 2$ so $a[i] ⇄ a[j]$. Then, $i = j = 5, j = i * 2 = 10 > right$ so this stage is done.

Our final heap should be:

The Sorting Process

So we’ve discovered how to construct a heap. How can we actually use this heap for sorting our data?

Let’s assume we’re given a heap of $n$ elements. In order to obtain the sorted elements, $n$ steps have to be executed:

• Pick up the element at the top of the heap (and store it somewhere). This allows us to get the smallest one among the $n$ elements.
• Reconstruct the remaining elements to form a heap.

Here, two questions arise. Where can we store those emerging top elements? Creating a new array $b[n]$ isn’t a good solution because it would double the amount of memory required for the algorithm. Also, how can we reconstruct the remaining elements to form a heap? Do we need to write something new do this or can we reuse something we’ve already done?

A solution for all of these questions is as follows:

• In each step, the leftmost element and the rightmost element of the current heap are exchanged.
• Then, let the new leftmost element sift down into its proper position.
• After $n - 1$ steps, the array will be sorted (in the reverse order).

This is how the solution is implemented:

right = n; 
// Index of the right-most element
// of the current heap

while (right > 1) {
	a[1] ⇄ a[right];
	right--;
	sift(a, 1, right);
}

Let’s get our hands dirty and sort the heap we’ve just constructed above, shall we? This is our constructed heap, now we’d like to sort all of the elements which form this heap.

First, exchange $a[1]$ with $a[right]$. Then we’re going to let the new $a[1]$ sift down to its proper position in the heap marked with $\lfloor --- \rfloor$:

I will only demonstrate the changes of the heap without much detail, since we’ve already discussed the sifting algorithm in the above section. If you want to see the sifting process as well, just click on the $\blacktriangleright$ button before the changes.

We will do this repeatedly until our array is sorted!

Performance Analysis of Heap Sort

The Heap Sort algorithm runs in $\mathcal{O}(n\log n)$ because it consists of two stages:

• The heap construction stage: The algorithm executes $\lfloor\frac{n}{2}\rfloor$ sift steps where each step runs in $\mathcal{O}(\log n)$ time. As a result, this stage takes $\mathcal{O}(n \log n)$ time.
• The sorting stage: The algorithm executes $n - 1$ steps where each step runs in $\mathcal{O}(\log n)$ time. Therefore, this stage takes $\mathcal{O}(n \log n)$ time.

As a result, the worst-case complexity of Heap Sort is $\mathcal{O}(n \log n)$, and this is also similar to the average case. For the best case, it is $\mathcal{O}(n)$ when every elements in the array is identical to each other.

Heap Sort only requires $\mathcal{O}(1)$ - constant space.

Quick Sort

The Quick Sort algorithm was developed in 1959 by Tony Hoare. It was selected as one of the 10 algorithms “with the greatest influence on the development and practice of science and engineering in the 20th century”.

Basic Concept of Quick Sort

Quick Sort is based on the idea of an array partition.

An Array Partition

An array partition is an arrangement of the array’s elements so that:

After a partition is achieved, $a_s$ will be in its final position in the sorted array.

We can continue sorting the two subarrays to the left and to the right of $a_s$ independently by the same method.

For example, assume that we have the array:

In the given array, $a_s = 5$ is in its final position because $\{4, 1, 3\} < 5 < \{6, 9, 8\}$. This position will never be visited again by the algorithm.

This is the implementation for the above idea:

QuickSort(a[], left, right) {
	if (left < right) {
		s = Partition(a, left, right);
		QuickSort(a, left, s - 1);
		QuickSort(a, s + 1, right);
	}
}

The Partition Function

The Partition() function starts by selecting a pivot $p$, which is an element of the (sub)array being partitioned. For simplicity, we’re going to assume that $p = a_{left}$.

The function will then scan the (sub)array from both ends, comparing the (sub)array’s elements to the pivot $p$.

• $i$: left to right scan, stops when encountering $a_i ≥ p$.
• $j$: right to left scan, stops when encountering $a_i ≤ p$.

After both scans stop, three situations may arise:

• If $i < j$:

  The function exchanges $a_i$ and $a_j$, then it resume the scans by incrementing $i$ and decrementing $j$ by $1$.

  $\hspace{1.2cm} i\rightarrow \leftarrow j \\ \begin{array}{|c|c|c|c|c|c|c|} \hline 5 & 3 & 1 & 7 & 6 & 2 & 9 \\ \hline \end{array} \\ \hspace{-0.5cm}\uparrow \hspace{1.3cm}\lfloor --- \rfloor \\ \hspace{-0.1cm}\text{pivot} \hspace{0.7cm} \text{swap \& resume} \\ \hspace{1.3cm}\text{the scan}$
• If $i > j$:

  The function will have partitioned the (sub)array after exchanging the pivot $p = a_{left}$ with $a_j$. The split position is $s = j$.

  $\hspace{0.5cm} i \rightarrow \\ \begin{array}{|c|c|c|c|c|} \hline 5 & \text{all are} ≤ p & 4 & 6 & \text{all are} ≥p \\ \hline \end{array}\\ \hspace{0.5cm} \leftarrow j \\[10pt]\\ \hspace{0.8cm} i \downarrow \\ \begin{array}{|c|c|c|c|c|} \hline 4 & \text{all are} ≤ p & 5 & 6 & \text{all are} ≥p \\ \hline \end{array}\\ \hspace{0.3cm} \uparrow j$
  • $a[j] = p = 5$: new value of $a[j]$; $p = a[j] = 4$: new pivot value
  • The array is separated by the element with the value $5$.
• If $i = j$:

  The value that two scanning indices are pointing to must be equal to $p$. Thus, we have the (sub)array partitioned, with the split position $s = i = j$.

  $\hspace{1cm} i \rightarrow \\ \begin{array}{|c|c|c|c|c|} \hline 5 & \text{all are} ≤ p & 5 & \text{all are} ≥p \\ \hline \end{array}\\ \leftarrow j \\$
  • If we swap $a[i] ⇄ a[j]$, it would be redundant. $p ⇄ a[j]$, if we do that it’s still correct but redundant). We should only return $i$ or $j$ as the split position in this case.

Let’s see how this Partition() function is implemented:

Partition(a[], left, right) {
	p = a[left];
	i = left;
	j = right + 1;
	do {
		do i++; while (a[i] < p);
		do j--; while (a[j] > p);
		a[i] ⇄ a[j];
	} while (i < j);
	a[i] ⇄ a[j]; // undo last swap when i ≥ j
	a[left] ⇄ a[j];
	return j;
} 

This is called the Hoare’s Partition Algorithm.

When this function runs, $i$ is less than $j$ ($i < j$) for most of the iterations, so the loop primarily handles this case.

If $i > j$, this only happens once per partition operation, at which point we need to undo the last swap ($a[i] ⇄ a[j]$). This is because in the last iteration where $i < j$, $a[i]$ and $a[j]$ were swapped unnecessarily before exiting the loop.

As for the final pivot swap ($a[left] ⇄ a[j]$), while it may be redundant when $i = j$, its time complexity is constant, making it an acceptable trade-off for maintaining the simplicity and clarity of the function.

Overall, the Partition() function is just a beautiful piece of code.

Performance Analysis of Quick Sort

In the Quick Sort algorithm, the basic operation is the comparisons in the do-while loop. Therefore, the time efficiency of Quick Sort depends on the value of $p$ selected in each partition.

• In the best case: The value of $p$ is always the median of the (sub)array, allowing the pivot to consistently divide the array into two nearly equal halves. This balanced partitioning results in a logarithmic number of recursive calls, each processing linear elements.
  $B(n) \in \Theta(n\log n)$
• In the worst case: The value of $p$ is always the maximum or minimum value of the (sub)array. In such cases, the depth of recursion becomes linear, and the algorithm degrades to quadratic time complexity.
  $W(n) \in \Theta(n^2)$
• In the average case: On average, even with random pivot selections, the partitions tend to be reasonably balanced, leading to efficient sorting times.
  $A(n) ≈ 1.39n\log_2n \in \Theta(n\log n)$

As for space efficiency, due to the recursive call stack, Quick Sort uses $\mathcal{O}(n)$ space.

Merge Sort

Merge Sort is a divide-and-conquer approach that was invented by John von Neumann in 1945.

Basic Concept of Merge Sort