Chapter Four

Advanced Sorting Algorithms

07/22/25 1
 Quick Sort
• Quick sort is the fastest known algorithm.
• It uses divide and conquer strategy.
• It has two phases:
– The partition phase and
– The sort phase
• Most of the work is done in the partition phase – it works
out where to divide the work.
• The sort phase simply sorts the two smaller problems that
are generated in the partition phase.

07/22/25 2
• Good Points
– It is in-place since it uses only a small auxiliary stack
– It requires only nlogn time to sort n items
– It has an extremely short inner loop
– It has been subjected to a thorough mathematical analysis;
a very precise statement can be made about performance
issues.
• Weak Points
– It is recursive. Especially if recursion is not available, the
implementation is extremely complicated.
– It requires quadratic (i.e. n2) time in the worst-case
– It is fragile i.e. a simple mistake in the implementation can
go unnoticed and cause it to perform badly.
07/22/25 3
• Algorithm
1. If there are one or less elements in the array to be sorted,
return immediately
2. Pick an element in the array to serve as a “pivot” point.
(Usually, the left-most element in the array is used)
3. Split the array into two parts – one with elements larger
than the pivot and the other with elements smaller than
the pivot.
4. Recursively sort the left part and the right part

07/22/25 4
• Implementation
Left = 0;
Right = n-1; /* n is the total number of
elements in the list*/
PivotPos = Left;
while(Left < Right){
if(PivotPos = = Left){
if(Data[Left] > Data[Right]){
swap(data[Left],
Data[Right]);
PivotPos = Right;
Left++;
}
else
Right– –;
}
07/22/25 5
 else {
if(Data[Left] > Data[Right]){
swap(data[Left],
Data[Right]);
PivotPos = Left;
Right – – ;
}
else
Left++;
}
}
• Note: Do the above algorithm recursively for both sub-arrays
until you find sorted list.

07/22/25 6
07/22/25 7
07/22/25 8
 Heap Sort
• Heap sort algorithm, as the name suggests, is based on the
concept of heaps.
• It begins by constructing a special type of binary tree,
called heap, out of the set of data which is to be sorted.
• Heap tree is a binary tree in which each node has a value
greater than both its children (if any).
• It is a complete binary tree. It uses a process called
"adjust” to accomplish its task (building a heap tree)
whenever a value is larger than its parent.
• The time complexity of heap sort is O(n log n).
• The root node of a Heap, by definition, is the maximum
of all the elements in the set of data constituting the
binary tree.
07/22/25 9
• Hence, the sorting process basically consists of extracting
the root node and reheaping the remaining set of elements
to obtain the next largest element till there are no more
elements left to heap.
• Elementary implementations usually employ two arrays,
one for the heap and the other to store the sorted data.
• But it is possible to use the same array to heap the
unordered list and compile the sorted list.
• This is usually done by swapping the root of the heap
with the end of the array and then excluding that element
from any subsequent reheaping.

07/22/25 10
• Algorithm
– Construct a binary tree
• The root node corresponds to Data [0].
• If we consider the index associated with a particular node to
be i,
– then the left child of this node corresponds to the element with
index 2 * i + 1 and
– the right child corresponds to the element with index 2 * i + 2.
– If any or both of these elements do not exist in the array, then
the corresponding child node does not exist either.
• Construct the heap tree from initial binary tree using "adjust"
process.

07/22/25 11
 • Do the following operations to sort
– Copy the root value into the array in its proper position
– Swap the root value with the lowest right most value
– Delete the lowest right most value
• Example: Sort the following list using heap sort
algorithm.
5 8 2 4 1 3 9 7 6 0
• Construct the initial binary tree

07/22/25 12
• Construct the heap tree

– Copy the root node value into the array in its proper
position;
– Swap the root node with the lowest right most node;
– delete the lowest right most value;
– adjust the heap tree;
– and repeat this process until the tree is empty.
07/22/25 13
07/22/25 14
07/22/25 15
07/22/25 16
07/22/25 17
• C++ Implementation
void heapify(int arr[], int n, int i) {
int largest = i;//Initialize largest as root
int left = 2 * i + 1; // left child
int right = 2 * i + 2; // right child
// If left child is larger than root
if (left < n && arr[left] > arr[largest])
largest = left;
/*If right child is larger than largest so
far*/
if (right < n && arr[right] > arr[largest])
largest = right;
// If largest is not root
if (largest != i) {
swap(arr[i], arr[largest]);
// Recursively heapify the affected sub-tree
heapify(arr, n, largest);
} }
07/22/25 18
 // Main function to perform heap sort
void heapSort(int arr[], int n) {
// Build max heap (rearrange array)
for (int i = n / 2 - 1; i >= 0; i--)
heapify(arr, n, i);
// One by one extract elements from heap
for (int i = n - 1; i > 0; i--) {
// Move current root to end
swap(arr[0], arr[i]);
// call max heapify on the reduced heap
heapify(arr, i, 0);
}
}

07/22/25 19
 Merge Sort
• Merge-sort is based on the divide-and-conquer paradigm.
• The merge-sort algorithm can be described in general
terms as consisting of the following three steps:
• Divide Step
– If a given array A has zero or one element, return S; it is
already sorted.
– Otherwise, divide A into two arrays, A1 and A2, each
containing about half of the elements of A
• Recursion Step
– Recursively sort A1 and A2
• Conquer Step
– Combine the elements back in A by merging the sorted
arrays A1 and A2 into a sorted sequence
07/22/25 20
• The heart of the Merge-sort algorithm is conquer step,
which merge two sorted sequences into a single sorted
sequence.
• The time complexity of Merge-sort algorithm is O(nlogn).
• Merge-sort required O(n) extra space.
• It is not in-place algorithm.
• Algorithm
1. Divide the array in to two halves.
2. Recursively sort the first n/2 items.
3. Recursively sort the last n/2 items.
4. Merge sorted items (using an auxiliary array).

07/22/25 21
• C++ Implementation
void mergeSort (int numbers[ ], int temp[ ],
int array_size) {
m_sort (numbers, temp, 0, array_size –
1);
}
void m_sort (int numbers[ ], int temp[ ], int
left, int right) {
int mid;
if (right > left) {
mid = (right + left) / 2;
m_sort (numbers, temp, left, mid);
m_sort(numbers, temp, mid + 1,
right);
merge(numbers,temp,left,mid+1,
right);
}
07/22/25
}
22
 void merge (int numbers[ ], int temp[ ], int
left, int mid, int
right) {
int i, left_end, num_elements, tmp_pos;
left_end = mid – 1;
tmp_pos = left;
num_elements = right – left + 1;
while((left <= left_end)&&(mid <= right)){
if (numbers[left] <= numbers[mid]) {
temp[tmp_pos] = numbers[left];
tmp_pos = tmp_pos + 1;
left = left + 1;
}

07/22/25 23
 else {
temp[tmp_pos] = numbers[mid];
tmp_pos = tmp_pos + 1;
mid = mid + 1;
}
}
while (left <= left_end) {
temp[tmp_pos] = numbers[left];
left = left + 1;
tmp_pos = tmp_pos + 1;
}
while (mid <= right) {
temp[tmp_pos] = numbers[mid];
mid = mid + 1;
tmp_pos = tmp_pos + 1;
}
07/22/25 24
 for (i = 0; i <= num_elements; i++) {
numbers[right] = temp[right];
right = right – 1;
}
}

07/22/25 25
• Example: Sort the following list using Merge-sort
algorithm.
5 8 2 4 1 3 9 7 6 0

07/22/25 26