Divide and Conquer algorithm, relies on a merge operation:

• How to combine two sorted arrays into a single sorted array?

ALGORITHM
if

Divide and Conquer algorithm, relies on a partition operation that, given a pivot, divides the array into two parts:

• Left part contains elements less than the pivot, and right part greater.

ALGORITHM
if

Partitioning process

Here, the split position is .

Heap Sort keeps the array as a max-heap:

• Complete binary tree
• Each node is no less than its children.

Repeatedly perform Maximum Key Deletion:

1. Exchange the root's key with the last key.
2. Decrease the heap size by 1.
3. Heapify the complete binary tree.