Sorting Algorithms
Open in the Padhaiko app7.1 Definition of sorting and its applications
Sorting
Sorting is the algorithmic process of rearranging a collection of elements (or records) into a permutation ordered according to a comparison relation on a key field:
- Ascending (Non-Decreasing) Order: .
- Descending (Non-Increasing) Order: .
7.2 Types of sorting: Internal/external sort, stable/unstable sort, in-place/ not in-place sort, adaptive/ non-adaptive sort
Sorting algorithms are classified along four orthogonal dimensions: where data resides during sorting, whether equal-key order is preserved, how much auxiliary memory is needed, and whether existing order in the input speeds up execution.
1. Internal Sort vs. External Sort
Internal and External Sorting
- Internal Sorting: All records to be sorted fit completely inside main memory (RAM), allowing fast random access to any element. Examples: Bubble Sort, Insertion Sort, Selection Sort, Shell Sort, Quick Sort, Heap Sort, Radix Sort.
- External Sorting: The dataset is too large to fit into RAM at once and resides on secondary storage (hard disks or SSDs). Because disk block I/O is orders of magnitude slower than RAM access, external sorting minimizes disk reads/writes by loading memory-sized chunks into RAM, sorting them into initial runs, and merging the runs using -way External Merge Sort.
| Aspect | Internal Sorting | External Sorting |
|---|---|---|
| Storage Medium | Main memory (RAM) only | Secondary storage (Disk / SSD) + RAM buffers |
| Dataset Size | Bounded by available RAM capacity | Arbitrarily large (gigabytes to petabytes) |
| Access Pattern | Fast random access to any index | Sequential block-level read/write I/O |
| Primary Bottleneck | CPU key comparisons and data movements | Disk I/O seek and transfer time |
| Representative Algorithms | Quick Sort, Heap Sort, Insertion Sort, Selection Sort | External -way Merge Sort, Polyphase Merge Sort |
2. Stable Sort vs. Unstable Sort
Stable and Unstable Sorting
Let two distinct records and have equal sort keys () with appearing before () in the original unsorted input:
- A sorting algorithm is stable if is guaranteed to appear before in the final sorted output.
- Examples: Bubble Sort, Insertion Sort, Merge Sort, Radix Sort.
- A sorting algorithm is unstable if equal-key records may have their relative order reversed (typically caused by long-range swaps across intervening elements).
- Examples: Selection Sort, Shell Sort, Quick Sort, Heap Sort.
For example, when sorting student records [(Ram, 85), (Sita, 92), (Hari, 85)] by marks in ascending order, a stable sort preserves (Ram, 85) before (Hari, 85) to yield [(Ram, 85), (Hari, 85), (Sita, 92)], whereas an unstable sort may output [(Hari, 85), (Ram, 85), (Sita, 92)].Stability is essential when sorting multi-attribute tables (e.g., sorting employees alphabetically by name first, and then stably sorting by department).
3. In-Place Sort vs. Not In-Place Sort
In-Place and Not In-Place Sorting
- In-Place Sort: Sorts the elements directly within the original input array using only constant auxiliary memory (or at most implicit call-stack space) for loop counters, pivot/key variables, and swaps.
- Examples: Bubble Sort, Insertion Sort, Selection Sort, Shell Sort, Heap Sort ( auxiliary space), and Quick Sort ( stack space).
- Not In-Place (Out-of-Place) Sort: Allocates extra auxiliary buffers proportional to the input size ( extra memory) to hold elements during sorting.
- Examples: Merge Sort ( temporary merge array) and Radix Sort ( output and bucket-count arrays).
4. Adaptive Sort vs. Non-Adaptive Sort
Adaptive and Non-Adaptive Sorting
- Adaptive Sort: Takes advantage of existing order (pre-sortedness) in the input array so that its time complexity decreases substantially when the input is already sorted or nearly sorted.
- Examples: Insertion Sort (drops from to on sorted input), Bubble Sort with swap flag (terminates in pass = on sorted input), and Shell Sort.
- Non-Adaptive Sort: Executes the exact same sequence of comparisons or passes regardless of the initial arrangement of the input data (its best-case, average-case, and worst-case complexities are identical).
- Examples: Selection Sort (always performs comparisons), Merge Sort (always ), Heap Sort (always ), and Radix Sort (always ).
7.3 Sorting algorithms and its efficiency: Bubble, insertion, selection, shell, quick, merge, radix and heap sorting
1. Bubble Sort
Principle: Bubble Sort is an exchange sort that repeatedly scans the array from left to right, comparing adjacent elements arr[j] and arr[j + 1] and swapping them if arr[j] > arr[j + 1]. After pass (), the -th largest element has "bubbled" to its final position at index . Adding a boolean swapped flag allows the algorithm to stop immediately if a pass makes zero swaps.
#include <stdio.h>
void bubbleSort(int arr[], int n) {
for (int i = 0; i < n - 1; i++) {
int swapped = 0;
for (int j = 0; j < n - 1 - i; j++) {
if (arr[j] > arr[j + 1]) {
int temp = arr[j];
arr[j] = arr[j + 1];
arr[j + 1] = temp;
swapped = 1;
}
}
if (!swapped) break; /* Array is already sorted */
}
}Trace on arr = [5, 1, 4, 2, 8] (Notes Example)
| Pass | Adjacent Comparisons & Swaps | Array After Pass | Sorted Suffix |
|---|---|---|---|
| Pass 1 | ; ; ; no swap | [1, 4, 2, 5, 8] | [8] |
| Pass 2 | no swap; ; no swap | [1, 2, 4, 5, 8] | [5, 8] |
| Pass 3 | no swap; no swap (swapped == 0 stop early) | [1, 2, 4, 5, 8] | [1, 2, 4, 5, 8] |
- Efficiency:
- Best Case (already sorted): comparisons, swaps (with
swappedflag). - Average & Worst Case (reverse sorted): comparisons and swaps .
- Auxiliary Space: (in-place). Stable: Yes. Adaptive: Yes (with flag).
- Best Case (already sorted): comparisons, swaps (with
2. Insertion Sort
Principle: Insertion Sort partitions the array into a sorted prefix arr[0 .. i-1] and an unsorted suffix arr[i .. n-1]. In iteration (), it picks key = arr[i], shifts all elements in arr[0 .. i-1] that are strictly greater than key one position to the right, and inserts key into the vacated slot—just like sorting playing cards in hand.
void insertionSort(int arr[], int n) {
for (int i = 1; i < n; i++) {
int key = arr[i];
int j = i - 1;
while (j >= 0 && arr[j] > key) {
arr[j + 1] = arr[j];
j = j - 1;
}
arr[j + 1] = key;
}
}Trace on arr = [4, 3, 2, 10, 12, 1, 5, 6] (Notes Example)
| Iteration () | key | Elements Shifted Right | Array After Insertion |
|---|---|---|---|
| Initial | — | — | [4, 3, 2, 10, 12, 1, 5, 6] |
| Shift | [3, 4, 2, 10, 12, 1, 5, 6] | ||
| Shift | [2, 3, 4, 10, 12, 1, 5, 6] | ||
| None () | [2, 3, 4, 10, 12, 1, 5, 6] | ||
| None () | [2, 3, 4, 10, 12, 1, 5, 6] | ||
| Shift | [1, 2, 3, 4, 10, 12, 5, 6] | ||
| Shift | [1, 2, 3, 4, 5, 10, 12, 6] | ||
| Shift | [1, 2, 3, 4, 5, 6, 10, 12] |
- Efficiency:
- Best Case (already sorted): Inner
whilecondition fails immediately each time comparisons, shifts . - Average Case (random order): About comparisons per step .
- Worst Case (reverse sorted): Step performs comparisons and shifts .
- Auxiliary Space: (in-place). Stable: Yes (uses
arr[j] > key, never moving equal elements pastkey). Adaptive: Yes.
- Best Case (already sorted): Inner
3. Selection Sort
Principle: In pass (), Selection Sort scans the entire unsorted subarray arr[i .. n-1] to find the index minIndex of its smallest element, and swaps arr[minIndex] with arr[i]. This grows the sorted prefix one element at a time using at most swaps.
void selectionSort(int arr[], int n) {
for (int i = 0; i < n - 1; i++) {
int minIndex = i;
for (int j = i + 1; j < n; j++) {
if (arr[j] < arr[minIndex]) {
minIndex = j;
}
}
int temp = arr[minIndex];
arr[minIndex] = arr[i];
arr[i] = temp;
}
}Trace on arr = [64, 25, 12, 22, 11] (Notes Example)
| Pass () | Unsorted Subarray | Minimum Found | Swap Performed | Array After Pass |
|---|---|---|---|---|
| Initial | [64, 25, 12, 22, 11] | — | — | [64, 25, 12, 22, 11] |
[64, 25, 12, 22, 11] | (index ) | Swap 64 11 | [11, 25, 12, 22, 64] | |
[25, 12, 22, 64] | (index ) | Swap 25 12 | [11, 12, 25, 22, 64] | |
[25, 22, 64] | (index ) | Swap 25 22 | [11, 12, 22, 25, 64] | |
[25, 64] | (index ) | Self-swap 25 25 | [11, 12, 22, 25, 64] |
- Efficiency:
- Best, Average, and Worst Case: Regardless of initial order, pass always performs comparisons:
- Swaps: At most swaps (useful when memory writes are costly).
- Auxiliary Space: (in-place). Stable: No (long-range swap can jump an element over an equal element, e.g.,
[4a, 4b, 1] -> [1, 4b, 4a]). Adaptive: No.
- Auxiliary Space: (in-place). Stable: No (long-range swap can jump an element over an equal element, e.g.,
4. Shell Sort
Principle: Invented by Donald Shell, Shell Sort generalizes Insertion Sort by comparing and shifting elements separated by a gap (increment) sequence (classically Shell's halving sequence ).
- Each pass -sorts the array (performing insertion sort independently on interleaved sublists
arr[k], arr[k+h], arr[k+2h], ...), allowing elements far out of place to leap multiple positions in a single swap. - By the time the final pass runs with (standard Insertion Sort), the array is already nearly sorted, so very few shifts are needed.
void shellSort(int arr[], int n) {
for (int gap = n / 2; gap > 0; gap /= 2) {
for (int i = gap; i < n; i++) {
int temp = arr[i];
int j;
for (j = i; j >= gap && arr[j - gap] > temp; j -= gap) {
arr[j] = arr[j - gap];
}
arr[j] = temp;
}
}
}Trace on arr = [33, 31, 40, 8, 12, 17, 25, 42] (, Notes Example)
| Pass / Gap | Interleaved Sublists Sorted | Array After Pass |
|---|---|---|
| Initial | — | [33, 31, 40, 8, 12, 17, 25, 42] |
| () | , , , | [12, 17, 25, 8, 33, 31, 40, 42] |
| () | Even indices (already sorted); Odd indices | [12, 8, 25, 17, 33, 31, 40, 42] |
| () | Standard insertion sort: swap , , | [8, 12, 17, 25, 31, 33, 40, 42] |
- Efficiency:
- Best Case: .
- Average Case: (or to for Hibbard/Sedgewick gaps).
- Worst Case: for Shell's halving sequence ( for Knuth/Hibbard sequences).
- Auxiliary Space: (in-place). Stable: No. Adaptive: Yes.
5. Quick Sort
Principle: Quick Sort is a divide-and-conquer exchange sort:
- Divide (Partition): Choose a pivot element from
arr[low .. high]and rearrange the subarray in-place so that all elements lie to the left of indexpi, the pivot itself is placed at its final sorted indexpi, and all elements lie to the right ofpi. - Conquer: Recursively apply
quickSort(arr, low, pi - 1)andquickSort(arr, pi + 1, high). - Combine: Nothing to do—the array is sorted in place.
void swap(int *a, int *b) {
int temp = *a;
*a = *b;
*b = temp;
}
int partition(int arr[], int low, int high) {
int pivot = arr[high]; /* Last element chosen as pivot */
int i = low - 1;
for (int j = low; j < high; j++) {
if (arr[j] <= pivot) {
i++;
swap(&arr[i], &arr[j]);
}
}
swap(&arr[i + 1], &arr[high]);
return i + 1;
}
void quickSort(int arr[], int low, int high) {
if (low < high) {
int pi = partition(arr, low, high);
quickSort(arr, low, pi - 1);
quickSort(arr, pi + 1, high);
}
}Trace on arr = [24, 27, 19, 9, 29, 14] (First-Element Pivot from Notes)
- Partitioning
[24, 27, 19, 9, 29, 14]withpivot = 24:- Scan
xright from index (A[1] = 27 > 24) andyleft from index (A[5] = 14 < 24); swap . - Advance
xacross to index (29 > 24) andyleft to index (9 < 24); pointers cross at index , so swap pivotA[0] = 24withA[3] = 19/9to place at index :
- Scan
- Left Subarray
[19, 14, 9]withpivot = 19:- Swap
19with9; remaining[9, 14]with pivot is already in order .
- Swap
- Right Subarray
[29, 27]withpivot = 29:- Swap
29with27.
- Swap
- Final Sorted Array:
[9, 14, 19, 24, 27, 29].
- Efficiency:
- Best Case (balanced split at every level):
- Average Case (random input): .
- Worst Case (already sorted or reverse-sorted when picking first/last element as pivot): One partition has elements and the other has :
- Auxiliary Space: average recursion stack depth; worst-case stack depth.
- Stable: No. Adaptive: No.
6. Merge Sort
Principle: Merge Sort is a stable divide-and-conquer algorithm with guaranteed performance:
- Divide: Split the array
A[left .. right]at midpointmid = (left + right) / 2into two halves of sizes and . - Conquer: Recursively sort
A[left .. mid]andA[mid + 1 .. right]. - Combine (Merge): Merge the two sorted subarrays into a single sorted sequence in linear time using two pointers
iandj.
void merge(int A[], int left, int mid, int right) {
int n1 = mid - left + 1;
int n2 = right - mid;
int L[n1], R[n2];
for (int i = 0; i < n1; i++) L[i] = A[left + i];
for (int j = 0; j < n2; j++) R[j] = A[mid + 1 + j];
int i = 0, j = 0, k = left;
while (i < n1 && j < n2) {
if (L[i] <= R[j]) A[k++] = L[i++];
else A[k++] = R[j++];
}
while (i < n1) A[k++] = L[i++];
while (j < n2) A[k++] = R[j++];
}
void mergeSort(int A[], int left, int right) {
if (left < right) {
int mid = left + (right - left) / 2;
mergeSort(A, left, mid);
mergeSort(A, mid + 1, right);
merge(A, left, mid, right);
}
}Trace on A = [24, 27, 19, 9, 29, 14] (Notes Example)
[24, 27, 19, 9, 29, 14]
/ \
[24, 27, 19] [9, 29, 14] <-- Divide
/ \ / \
[24] [27, 19] [9] [29, 14]
/ \ / \
[27] [19] [29] [14]
\ / \ /
[24] [19, 27] [9] [14, 29] <-- Merge
\ / \ /
[19, 24, 27] [9, 14, 29]
\ /
[9, 14, 19, 24, 27, 29] <-- Final Sorted- Efficiency:
- Best, Average, and Worst Case: Always splits the array into two equal halves across levels and performs work per level:
- Auxiliary Space: temporary arrays
L[]andR[](not in-place).- Stable: Yes (because
L[i] <= R[j]picks the left-half element first on ties). Adaptive: No.
- Stable: Yes (because
7. Radix Sort
Principle: Radix Sort is a non-comparative integer sorting algorithm. Instead of comparing full keys, LSD (Least Significant Digit) Radix Sort processes numbers digit by digit from the units place () up to the most significant digit (), applying a stable bucket/counting sort at every digit pass.
int getMax(int arr[], int n) {
int max = arr[0];
for (int i = 1; i < n; i++)
if (arr[i] > max) max = arr[i];
return max;
}
void countSort(int arr[], int n, int exp) {
int output[n], count[10] = {0};
for (int i = 0; i < n; i++)
count[(arr[i] / exp) % 10]++;
for (int i = 1; i < 10; i++)
count[i] += count[i - 1];
for (int i = n - 1; i >= 0; i--) {
int digit = (arr[i] / exp) % 10;
output[count[digit] - 1] = arr[i];
count[digit]--;
}
for (int i = 0; i < n; i++)
arr[i] = output[i];
}
void radixSort(int arr[], int n) {
int max = getMax(arr, n);
for (int exp = 1; max / exp > 0; exp *= 10)
countSort(arr, n, exp);
}Trace on arr = [170, 45, 75, 90, 802, 24, 2, 66] (Notes Example)
The maximum number is , which has decimal digits ( buckets ):
| Pass | Digit Place () | Non-Empty Buckets () | Array After Pass |
|---|---|---|---|
| Initial | — | — | [170, 45, 75, 90, 802, 24, 2, 66] |
| Pass 1 | Units () | , , , , | [170, 90, 802, 2, 24, 45, 75, 66] |
| Pass 2 | Tens () | , , , , , | [802, 2, 24, 45, 66, 170, 75, 90] |
| Pass 3 | Hundreds () | , , | [2, 24, 45, 66, 75, 90, 170, 802] |
- Efficiency:
- Best, Average, and Worst Case: Each of the passes executes Counting Sort in time (where is the radix/base, e.g., ):
- Auxiliary Space: (for
output[n]andcount[k]). Stable: Yes (stability of the inner Counting Sort is mandatory for Radix Sort to work). Adaptive: No.
8. Heap Sort
Binary Heap and Heap Property
A binary heap is a complete binary tree stored compactly in an array a[0 .. n-1] without pointers. For any node at -based index :
- Max-Heap Property: Every parent is greater than or equal to its children (), so the maximum element is always at the root
a[0]. - Min-Heap Property: Every parent is less than or equal to its children (), so the minimum element is always at the root
a[0].
Two Phases of Heap Sort (Ascending Order):
- Phase 1 — Build Max-Heap ( time): Starting from the last internal node down to , call
heapify(a, n, i)to sift smaller elements down and establish the Max-Heap property. - Phase 2 — Repeated Extraction ( time): For down to :
- Swap the maximum element at root
a[0]with the last heap elementa[i](placing the maximum into its final sorted position at the end of the array). - Reduce the active heap size to and call
heapify(a, i, 0)in time to restore the Max-Heap property.
- Swap the maximum element at root
void heapify(int a[], int n, int i) {
int largest = i;
int left = 2 * i + 1;
int right = 2 * i + 2;
if (left < n && a[left] > a[largest])
largest = left;
if (right < n && a[right] > a[largest])
largest = right;
if (largest != i) {
int temp = a[i];
a[i] = a[largest];
a[largest] = temp;
heapify(a, n, largest);
}
}
void heapSort(int a[], int n) {
/* Phase 1: Build Max-Heap bottom-up */
for (int i = n / 2 - 1; i >= 0; i--)
heapify(a, n, i);
/* Phase 2: Extract max one by one */
for (int i = n - 1; i > 0; i--) {
int temp = a[0];
a[0] = a[i];
a[i] = temp;
heapify(a, i, 0);
}
}Trace on a = [22, 13, 17, 11, 10, 14, 12] (Notes Example)
| Step | Operation | Active Heap | Sorted Suffix | Full Array State |
|---|---|---|---|---|
| Build | Already satisfies Max-Heap (; ; ) | [22, 13, 17, 11, 10, 14, 12] | [] | [22, 13, 17, 11, 10, 14, 12] |
| 1 | Swap ; heapify size () | [17, 13, 14, 11, 10, 12] | [22] | [17, 13, 14, 11, 10, 12, 22] |
| 2 | Swap ; heapify size () | [14, 13, 12, 11, 10] | [17, 22] | [14, 13, 12, 11, 10, 17, 22] |
| 3 | Swap ; heapify size () | [13, 11, 12, 10] | [14, 17, 22] | [13, 11, 12, 10, 14, 17, 22] |
| 4 | Swap ; heapify size () | [12, 11, 10] | [13, 14, 17, 22] | [12, 11, 10, 13, 14, 17, 22] |
| 5 | Swap ; heapify size () | [11, 10] | [12, 13, 14, 17, 22] | [11, 10, 12, 13, 14, 17, 22] |
| 6 | Swap ; size remaining | [10] | [11, 12, 13, 14, 17, 22] | [10, 11, 12, 13, 14, 17, 22] |
- Efficiency:
- Best, Average, and Worst Case: Building the heap takes and extracting elements takes , giving in all cases.
- Auxiliary Space: (in-place). Stable: No. Adaptive: No.
Master Comparison of All 8 Sorting Algorithms
| Algorithm | Best Time | Average Time | Worst Time | Auxiliary Space | Stable? | In-Place? | Adaptive? |
|---|---|---|---|---|---|---|---|
| Bubble Sort | Yes | Yes | Yes (with flag) | ||||
| Insertion Sort | Yes | Yes | Yes | ||||
| Selection Sort | No | Yes | No | ||||
| Shell Sort | No | Yes | Yes | ||||
| Quick Sort | No | Yes | No | ||||
| Merge Sort | Yes | No | No | ||||
| Radix Sort | Yes | No | No | ||||
| Heap Sort | No | Yes | No |
Worked Examples
7.1
Sort the -element array 92, 83, 22, 49, 36, 98, 12, 9, 70, 51 in ascending order using both (a) Insertion Sort and (b) Shell Sort (with halving gaps ).
Part (a) — Tracing Insertion Sort pass by pass:
- Initial:
[92, 83, 22, 49, 36, 98, 12, 9, 70, 51] - (
key = 83):[83, 92, 22, 49, 36, 98, 12, 9, 70, 51] - (
key = 22):[22, 83, 92, 49, 36, 98, 12, 9, 70, 51] - (
key = 49):[22, 49, 83, 92, 36, 98, 12, 9, 70, 51] - (
key = 36):[22, 36, 49, 83, 92, 98, 12, 9, 70, 51] - (
key = 98):[22, 36, 49, 83, 92, 98, 12, 9, 70, 51](no shift) - (
key = 12):[12, 22, 36, 49, 83, 92, 98, 9, 70, 51] - (
key = 9):[9, 12, 22, 36, 49, 83, 92, 98, 70, 51] - (
key = 70):[9, 12, 22, 36, 49, 70, 83, 92, 98, 51] - (
key = 51):[9, 12, 22, 36, 49, 51, 70, 83, 92, 98]
Part (b) — Tracing Shell Sort with , , and :
- Pass 1 (): Compare pairs :
- ; ; ; ; .
- Array after :
[92, 12, 9, 49, 36, 98, 83, 22, 70, 51].
- Pass 2 (): Insertion-sort the two interleaved sublists of stride :
- Even indices : .
- Odd indices : .
- Interleaved array after :
[9, 12, 36, 22, 70, 49, 83, 51, 92, 98].
- Pass 3 (): Standard insertion sort on the nearly sorted array swaps only , , and shifts past :
- Final sorted array:
[9, 12, 22, 36, 49, 51, 70, 83, 92, 98].
- Final sorted array:
Both Insertion Sort and Shell Sort () yield the sorted array [9, 12, 22, 36, 49, 51, 70, 83, 92, 98].
7.2
Trace Quick Sort step-by-step on the -element array 30, 25, 78, 19, 48, 28, 21, 44, 120 using the first element of each subarray as the pivot.
First partition on A[0..8] = [30, 25, 78, 19, 48, 28, 21, 44, 120] with pivot = 30: Elements are ( elements), so pivot 30 lands at index :
- Pointer
xstops atA[2] = 78(); pointerystops atA[6] = 21(); swap . - Pointer
xstops atA[4] = 48(); pointerystops atA[5] = 28(); swap . - Pointers cross at index (
A[4] = 28); swap pivotA[0] = 30withA[4] = 28:
Recursively sorting Left Subarray A[0..3] = [28, 25, 21, 19]:
pivot = 28: all of are ; swap28with19.- On
[19, 25, 21]withpivot = 19: both , so19stays at index . - On
[25, 21]withpivot = 25: swap25with21. - Left half is now completely sorted:
[19, 21, 25, 28].
Recursively sorting Right Subarray A[5..8] = [48, 78, 44, 120]:
pivot = 48:xstops at78(),ystops at44(); swap ; swap pivot48with44.- Left sub-partition
[44]has element (sorted). - Right sub-partition
[78, 120]withpivot = 78has , so78stays at index and[120]is sorted.
The sorted array produced by Quick Sort is [19, 21, 25, 28, 30, 44, 48, 78, 120].
7.3
Sort the -element array 42, 36, 56, 21, 63, 72, 62, 15 using Max-Heap Sort, showing both the bottom-up Max-Heap construction and each extraction + heapify step.
Phase 1 — Building the Max-Heap bottom-up (, start at down to ): Initial array: [42, 36, 56, 21, 63, 72, 62, 15].
- (
a[3] = 21, childa[7] = 15): , no change. - (
a[2] = 56, childrena[5] = 72, a[6] = 62): swap . - (
a[1] = 36, childrena[3] = 21, a[4] = 63): swap . - (
a[0] = 42, children63, 72): swap at index , then compare with children of index (56, 62) and swap at index :
Phase 2 — Extracting the maximum one by one and restoring the Max-Heap:
| Step | Swap Root a[0] with a[i] | Heap Size | Sift-Down Path in heapify | Array After heapify |
|---|---|---|---|---|
| 1 | () | [63, 36, 62, 21, 15, 56, 42 | 72] | ||
| 2 | () | [62, 36, 56, 21, 15, 42 | 63, 72] | ||
| 3 | () | [56, 36, 42, 21, 15 | 62, 63, 72] | ||
| 4 | () | [42, 36, 15, 21 | 56, 62, 63, 72] | ||
| 5 | () | [36, 21, 15 | 42, 56, 62, 63, 72] | ||
| 6 | () | [21, 15 | 36, 42, 56, 62, 63, 72] | ||
| 7 | () | Done | [15, 21, 36, 42, 56, 62, 63, 72] |
- Constructed Max-Heap:
[72, 63, 62, 21, 36, 56, 42, 15]. - Final Sorted Array:
[15, 21, 36, 42, 56, 62, 63, 72].
7.4
Sort the numbers 14, 2, 205, 978, 121, 4, 34, 1110, 666, 840 using LSD Radix Sort, showing the array state after each digit pass.
Determining the number of passes: The largest number is , which has decimal digits. Pad each number conceptually to digits: 0014, 0002, 0205, 0978, 0121, 0004, 0034, 1110, 0666, 0840.
Executing the stable bucket passes ():
| Pass | Digit Place | Bucket Contents () | Array After Pass |
|---|---|---|---|
| Pass 1 | Units () | , , , , , , | [1110, 840, 121, 2, 14, 4, 34, 205, 666, 978] |
| Pass 2 | Tens () | , , , , , , | [2, 4, 205, 1110, 14, 121, 34, 840, 666, 978] |
| Pass 3 | Hundreds () | , , , , , | [2, 4, 14, 34, 1110, 121, 205, 666, 840, 978] |
| Pass 4 | Thousands () | , | [2, 4, 14, 34, 121, 205, 666, 840, 978, 1110] |
After passes (units, tens, hundreds, thousands), the sorted sequence is [2, 4, 14, 34, 121, 205, 666, 840, 978, 1110].
Exercises
Exercises
Differentiate between internal sorting and external sorting. Consider the following Max-Heap: 50, 30, 20, 15, 10, 8, 16. Insert a new node with value 55 into this Max-Heap and show the step-by-step sifting-up process.
Difference between internal and external sorting:
- Internal sorting holds all records in main memory (RAM) and uses random-access comparisons (e.g., Quick Sort, Heap Sort, Insertion Sort).
- External sorting handles datasets larger than RAM stored on disk/SSD by sorting memory-sized chunks into runs and merging them via -way External Merge Sort to minimize disk I/O.
Inserting 55 into Max-Heap a[0..6] = [50, 30, 20, 15, 10, 8, 16]:
- Append at next leaf index :
- Sift up (compare with parent , where
a[3] = 15): Since , swapa[7]anda[3]:
- Compare with parent , where
a[1] = 30: Since , swapa[3]anda[1]:
- Compare with root , where
a[0] = 50: Since , swapa[1]anda[0]:
Internal sort runs entirely in RAM whereas external sort processes disk-resident datasets via run generation and -way merging. Inserting 55 at index sifts up along to yield the Max-Heap [55, 50, 20, 30, 10, 8, 16, 15].
Explain Selection Sort with its algorithm and time complexity. Trace Selection Sort step-by-step on the data sequence 40, 90, 20, -10, 30, 5, 60, 100, 80 and compute the exact number of key comparisons performed.
Algorithm and complexity of Selection Sort: In pass (), Selection Sort scans arr[i .. n-1] to find the index minIndex of the minimum element and swaps arr[i] with arr[minIndex]. For elements, it always performs:
Pass-by-pass trace on [40, 90, 20, -10, 30, 5, 60, 100, 80]:
- Pass 1 (): Min in
arr[0..8]is-10(index ). Swap40-10:[-10, 90, 20, 40, 30, 5, 60, 100, 80] - Pass 2 (): Min in
arr[1..8]is5(index ). Swap905:[-10, 5, 20, 40, 30, 90, 60, 100, 80] - Pass 3 (): Min in
arr[2..8]is20(already at index ):[-10, 5, 20, 40, 30, 90, 60, 100, 80] - Pass 4 (): Min in
arr[3..8]is30(index ). Swap4030:[-10, 5, 20, 30, 40, 90, 60, 100, 80] - Pass 5 (): Min in
arr[4..8]is40(already at index ):[-10, 5, 20, 30, 40, 90, 60, 100, 80] - Pass 6 (): Min in
arr[5..8]is60(index ). Swap9060:[-10, 5, 20, 30, 40, 60, 90, 100, 80] - Pass 7 (): Min in
arr[6..8]is80(index ). Swap9080:[-10, 5, 20, 30, 40, 60, 80, 100, 90] - Pass 8 (): Min in
arr[7..8]is90(index ). Swap10090:[-10, 5, 20, 30, 40, 60, 80, 90, 100]
Selection Sort runs in time ( comparisons for ) and produces the sorted sequence [-10, 5, 20, 30, 40, 60, 80, 90, 100].
Explain Merge Sort and trace all divide and merge steps to sort the data sequence 85, 76, 46, 92, 30, 41, 12.
Divide-and-conquer phases of Merge Sort:
- Split (
[85, 76, 46, 92, 30, 41, 12]):- Left half ( elements):
[85, 76, 46, 92][85, 76]and[46, 92][85], [76], [46], [92]. - Right half ( elements):
[30, 41, 12][30, 41]and[12][30], [41], [12].
- Left half ( elements):
Bottom-up Merge Steps:
- Level 1 merges (pairs):
- Merge
[85]and[76]. - Merge
[46]and[92]. - Merge
[30]and[41](and[12]stays[12]).
- Merge
- Level 2 merges:
- Merge
[76, 85]and[46, 92]. - Merge
[30, 41]and[12].
- Merge
- Level 3 final merge:
- Merge
[46, 76, 85, 92]and[12, 30, 41].
- Merge
Merge Sort recursively splits the -element array to singletons and merges them in time to yield [12, 30, 41, 46, 76, 85, 92].
Compare Quick Sort and Merge Sort. Then trace the sorting steps in LSD Radix Sort for the data: 345, 654, 934, 123, 056, 072, 555, 808, 911, 057.
Comparison between Quick Sort and Merge Sort:
| Aspect | Quick Sort | Merge Sort |
|---|---|---|
| Partitioning | By value around a pivot (unequal split sizes possible) | By index at the exact midpoint |
| Worst-Case Time | (when pivot is extreme element) | (guaranteed in all cases) |
| Auxiliary Space | stack space (in-place) | auxiliary merge buffer (not in-place) |
| Stability | Unstable | Stable |
Tracing 3-pass LSD Radix Sort on 345, 654, 934, 123, 056, 072, 555, 808, 911, 057:
- Pass 1 — Units Digit ():
- , , , , , , , .
- After Pass 1:
[911, 072, 123, 654, 934, 345, 555, 056, 057, 808].
- Pass 2 — Tens Digit ():
- , , , , , , .
- After Pass 2:
[808, 911, 123, 934, 345, 654, 555, 056, 057, 072].
- Pass 3 — Hundreds Digit ():
- , , , , , , .
- After Pass 3:
[056, 057, 072, 123, 345, 555, 654, 808, 911, 934].
Quick Sort is in-place ( stack) and unstable with worst case, whereas Merge Sort is stable with worst case and extra space. LSD Radix Sort yields [056, 057, 072, 123, 345, 555, 654, 808, 911, 934].
Provide the best-case, average-case, and worst-case time complexities in Big-Oh notation for Bubble Sort, Insertion Sort, Selection Sort, and Merge Sort. Then trace Bubble Sort pass-by-pass on 16, 36, 24, 37, 15 and state the total number of swaps performed.
Asymptotic time complexity table:
| Algorithm | Best Case | Average Case | Worst Case |
|---|---|---|---|
| Bubble Sort | |||
| Insertion Sort | |||
| Selection Sort | |||
| Merge Sort |
Tracing Bubble Sort on [16, 36, 24, 37, 15] ():
- Pass 1 ( comparisons):
- no swap; ; no swap; ( swaps).
- Pass 2 ( comparisons):
- no swap; no swap; ( swap).
- Pass 3 ( comparisons):
- no swap; ( swap).
- Pass 4 ( comparison):
- ( swap).
- Total comparisons ; total swaps .
Bubble Sort performs comparisons and swaps across passes to produce [15, 16, 24, 36, 37].
Explain why Shell Sort is considered an adaptive improvement over Insertion Sort, and trace Shell Sort on the -element array 36, 25, 40, 2, 7, 80, 15 using gaps .
Why Shell Sort improves upon Insertion Sort: Standard Insertion Sort moves elements only position per shift, so an element far from its destination requires up to shifts. Shell Sort first -sorts the array with large strides (), moving elements across long distances in a single exchange so that the final pass encounters an almost-sorted array and runs in near-linear time.
Tracing Shell Sort on [36, 25, 40, 2, 7, 80, 15] ():
- Pass 1 ():
- Sublist 0 (indices ): .
- Sublist 1 (indices ): .
- Sublist 2 (indices ): .
- Array after :
[2, 7, 40, 15, 25, 80, 36].
- Pass 2 ():
- Standard insertion sort shifts
40past15, 25() and shifts40, 80past36: - Final sorted array:
[2, 7, 15, 25, 36, 40, 80].
- Standard insertion sort shifts
After , the array becomes [2, 7, 40, 15, 25, 80, 36]; after , the final sorted array is [2, 7, 15, 25, 36, 40, 80].