Advanced Sorting | Advanced Data Structures

LEARNING GOALS

🎯 Learning Objectives

After completing this level, you should be able to:

Distinguish comparison and non-comparison sorting.
Explain stability, in-place behavior, adaptiveness and external sorting.
Trace Merge, Quick and Shell Sort.
Apply Counting, Radix and Bucket Sort under suitable key constraints.
Implement all six methods in C and explain their important operations.
Compare best, average and worst-case performance.
Select an algorithm for practical and interview scenarios.

SORTING PROPERTIES

🧭 1. How Do We Compare Sorting Algorithms?

Stable

Equal keys preserve their original relative order.

In Place

The algorithm uses only small auxiliary memory.

Adaptive

Existing order helps reduce the work.

Online

Items can be processed as they arrive.

Comparison Sort

Ordering decisions come from comparing pairs of keys.

General lower bound: Ω(n log n)

Non-Comparison Sort

Uses key digits, ranges or distribution assumptions.

Can achieve linear time under constraints

Important: O(n) sorting does not violate the comparison lower bound because Counting, Radix and Bucket Sort use information beyond pairwise comparisons.

DIVIDE AND CONQUER

🧩 2. Merge Sort

Merge Sort divides the array into halves until single-element ranges remain, then combines sorted halves.

1

Divide

Split at the middle index.

2

Recurse Left

Sort the left half.

3

Recurse Right

Sort the right half.

4

Merge

Repeatedly copy the smaller front value.

Worked example

[38, 27, 43, 3, 9, 82] → divide into smaller ranges → merge [27, 38, 43] and [3, 9, 82] → [3, 9, 27, 38, 43, 82].

🔹 Step-by-Step Algorithm

If the current range has zero or one element, return.
Compute the middle index using low + (high - low) / 2.
Recursively sort the left range low…mid.
Recursively sort the right range mid + 1…high.
Compare the first unmerged values of both halves.
Copy the smaller value into temporary storage, then copy any leftovers.
Copy the merged values back into the original array.

Guarantee

Its running time is independent of initial order.

Best/Average/Worst: O(n log n)

Trade-off

Array merging normally requires auxiliary storage.

Extra space: O(n)

Merge Sort is stable and works especially well for linked lists and external files, where sequential access is preferred.

💻 Complete C Program — Merge SortView program

This implementation reuses one temporary array throughout the recursion.

#include <stdio.h>

#define MAX 100

void merge(int a[], int temp[], int low, int mid, int high) {
    int i = low, j = mid + 1, k = low;

    while (i <= mid && j <= high) {
        if (a[i] <= a[j])
            temp[k++] = a[i++];
        else
            temp[k++] = a[j++];
    }

    while (i <= mid) temp[k++] = a[i++];
    while (j <= high) temp[k++] = a[j++];

    for (i = low; i <= high; i++)
        a[i] = temp[i];
}

void mergeSort(int a[], int temp[], int low, int high) {
    if (low >= high) return;

    int mid = low + (high - low) / 2;
    mergeSort(a, temp, low, mid);
    mergeSort(a, temp, mid + 1, high);
    merge(a, temp, low, mid, high);
}

int main(void) {
    int n, a[MAX], temp[MAX];
    scanf("%d", &n);

    if (n < 1 || n > MAX) return 1;
    for (int i = 0; i < n; i++) scanf("%d", &a[i]);

    mergeSort(a, temp, 0, n - 1);

    for (int i = 0; i < n; i++) printf("%d ", a[i]);
    return 0;
}

Sample Input

6
38 27 43 3 9 82

Sample Output

3 9 27 38 43 82

PARTITIONING

⚡ 3. Quick Sort

Quick Sort chooses a pivot, partitions the array, then recursively sorts values on both sides of the pivot.

Lomuto invariant: before processing index j, values in low…i are ≤ pivot, values in i+1…j−1 are > pivot and j…high−1 are unclassified.

Worked example

For [8, 3, 1, 7, 0, 10, 2], choose pivot 2. Partitioning places 0, 1 before it and larger values after it, so the pivot reaches its final index before the two sides are sorted recursively.

🔹 Step-by-Step Algorithm

If low >= high, the range is already sorted.
Choose a pivot; the Lomuto method uses the last element.
Maintain i as the end of the “≤ pivot” region.
Scan j from low to high - 1.
When a[j] <= pivot, increase i and swap.
Place the pivot at i + 1.
Recursively sort the ranges on the left and right of the pivot.

Good Pivot

Creates two reasonably balanced subarrays.

Bad Pivot

Creates a 0 and n−1 split repeatedly.

Randomized Pivot

Reduces the chance of consistently poor input-dependent splits.

Three-Way Partition

Handles many duplicate keys efficiently.

Time: average O(n log n), worst O(n²). Space: O(log n) average recursion; Quick Sort is generally in-place but not stable.

💻 Complete C implementation available below

The full Lomuto program is paired with a statement-by-statement tracer.

View Quick Sort Program ↓

GAP-BASED INSERTION

🪜 4. Shell Sort

Shell Sort performs insertion sorting on elements separated by a gap. The gap decreases until the final pass uses gap 1.

Common simple sequence: n/2, n/4, …, 1. Better gap sequences often improve performance, so Shell Sort complexity depends strongly on this choice.

Worked example

For [12, 34, 54, 2, 3], gap 2 compares values two places apart and moves 3 and 2 closer to the front. The final gap-1 pass finishes with [2, 3, 12, 34, 54].

🔹 Step-by-Step Algorithm

Start with a gap such as n / 2.
For every index from gap to n - 1, save the current value.
Compare it with values one gap behind.
Shift larger gap-separated values to the right.
Insert the saved value into its correct gap-sorted position.
Reduce the gap and repeat until the gap becomes 1.

Why It Helps

Large gaps move far-away values closer to their final positions early.

In-place: O(1) auxiliary space

Limitation

It is not stable and has no single complexity for every gap sequence.

Simple halving worst case: O(n²)

💻 Complete C Program — Shell SortView program

This version uses the simple halving gap sequence.

#include <stdio.h>

#define MAX 100

void shellSort(int a[], int n) {
    for (int gap = n / 2; gap > 0; gap /= 2) {
        for (int i = gap; i < n; i++) {
            int value = a[i];
            int j = i;

            while (j >= gap && a[j - gap] > value) {
                a[j] = a[j - gap];
                j -= gap;
            }
            a[j] = value;
        }
    }
}

int main(void) {
    int n, a[MAX];
    scanf("%d", &n);

    if (n < 1 || n > MAX) return 1;
    for (int i = 0; i < n; i++) scanf("%d", &a[i]);

    shellSort(a, n);

    for (int i = 0; i < n; i++) printf("%d ", a[i]);
    return 0;
}

Sample Input

5
12 34 54 2 3

Sample Output

2 3 12 34 54

KEY FREQUENCIES

🔢 5. Counting Sort

Counting Sort counts how many times each integer key occurs. Cumulative counts can place records into a stable output array.

1

Find Range

Identify minimum and maximum keys.

2

Count

Build the frequency array.

3

Accumulate

Convert counts into ending positions.

4

Place

Scan input right to left for stability.

Worked example

For [4, 2, 2, 8, 3, 3, 1], the frequencies for 1, 2, 3, 4 and 8 are 1, 2, 2, 1 and 1. Expanding them in key order produces [1, 2, 2, 3, 3, 4, 8].

🔹 Step-by-Step Algorithm

Find the minimum and maximum keys.
Create a count array for the range minimum…maximum.
Count each input using the offset value - minimum.
Convert frequencies to cumulative positions.
Scan the input from right to left and place each value in the output.
Copy the stable output back into the input array.

Complexity: O(n + k) time and O(n + k) space, where k is the key range. It is attractive only when k is not excessively larger than n.

Negative keys: use an offset such as count[value − minimum]; never use a negative value directly as an array index.

💻 Complete C Program — Stable Counting SortView program

The minimum-value offset lets this program handle negative integers as well as positive integers.

#include <stdio.h>
#include <stdlib.h>

#define MAX 100

int countingSort(int a[], int n) {
    int minimum = a[0], maximum = a[0];
    int output[MAX];

    for (int i = 1; i < n; i++) {
        if (a[i] < minimum) minimum = a[i];
        if (a[i] > maximum) maximum = a[i];
    }

    int range = maximum - minimum + 1;
    int *count = calloc((size_t)range, sizeof(int));
    if (count == NULL) return 0;

    for (int i = 0; i < n; i++)
        count[a[i] - minimum]++;

    for (int i = 1; i < range; i++)
        count[i] += count[i - 1];

    for (int i = n - 1; i >= 0; i--) {
        int key = a[i] - minimum;
        output[--count[key]] = a[i];
    }

    for (int i = 0; i < n; i++) a[i] = output[i];
    free(count);
    return 1;
}

int main(void) {
    int n, a[MAX];
    scanf("%d", &n);

    if (n < 1 || n > MAX) return 1;
    for (int i = 0; i < n; i++) scanf("%d", &a[i]);

    if (!countingSort(a, n)) return 1;

    for (int i = 0; i < n; i++) printf("%d ", a[i]);
    return 0;
}

Sample Input

7
4 -2 2 8 3 3 1

Sample Output

-2 1 2 3 3 4 8

DIGIT-BY-DIGIT ORDERING

🧮 6. Radix Sort

LSD Radix Sort processes digits from least significant to most significant. Each digit pass must use a stable sub-sort.

Example passes: ones → tens → hundreds. After every stable pass, all processed lower-order digits remain correctly ordered.

Worked example

For [170, 45, 75, 90, 802, 24, 2, 66], stable passes on the ones, tens and hundreds digits finally produce [2, 24, 45, 66, 75, 90, 170, 802].

🔹 Step-by-Step Algorithm

Find the largest key to determine the number of digit passes.
Start with exponent 1 for the ones digit.
Use stable Counting Sort on digit (value / exponent) % 10.
Copy the digit-sorted output back to the array.
Multiply the exponent by 10.
Repeat until the largest value has no unprocessed digits.

Time

d passes over n keys using base b.

O(d(n + b))

Requirements

Keys must be separable into digits or fixed-position symbols.

Stable digit sort required

Program scope: the following introductory LSD implementation accepts non-negative decimal integers. Signed values need a defined sign-handling strategy.

💻 Complete C Program — LSD Radix SortView program

Stable Counting Sort is used for each decimal digit.

#include <stdio.h>

#define MAX 100

int getMaximum(const int a[], int n) {
    int maximum = a[0];
    for (int i = 1; i < n; i++)
        if (a[i] > maximum) maximum = a[i];
    return maximum;
}

void countingSortByDigit(int a[], int n, int exponent) {
    int output[MAX] = {0};
    int count[10] = {0};

    for (int i = 0; i < n; i++)
        count[(a[i] / exponent) % 10]++;

    for (int i = 1; i < 10; i++)
        count[i] += count[i - 1];

    for (int i = n - 1; i >= 0; i--) {
        int digit = (a[i] / exponent) % 10;
        output[--count[digit]] = a[i];
    }

    for (int i = 0; i < n; i++) a[i] = output[i];
}

void radixSort(int a[], int n) {
    int maximum = getMaximum(a, n);
    for (int exponent = 1; maximum / exponent > 0; ) {
        countingSortByDigit(a, n, exponent);
        if (exponent > maximum / 10) break;
        exponent *= 10;
    }
}

int main(void) {
    int n, a[MAX];
    scanf("%d", &n);

    if (n < 1 || n > MAX) return 1;
    for (int i = 0; i < n; i++) {
        scanf("%d", &a[i]);
        if (a[i] < 0) return 1;
    }

    radixSort(a, n);

    for (int i = 0; i < n; i++) printf("%d ", a[i]);
    return 0;
}

Sample Input

8
170 45 75 90 802 24 2 66

Sample Output

2 24 45 66 75 90 170 802

DISTRIBUTION BY RANGE

🪣 7. Bucket Sort

Bucket Sort distributes values into range-based containers, sorts each bucket and concatenates the buckets.

Worked example

For [0.42, 0.32, 0.23, 0.52, 0.25, 0.47, 0.51], values are placed into interval buckets, each bucket is sorted, and the buckets are joined as [0.23, 0.25, 0.32, 0.42, 0.47, 0.51, 0.52].

🔹 Step-by-Step Algorithm

Create a suitable number of empty buckets.
Map every value to a bucket using its range or distribution.
Sort the values inside each non-empty bucket.
Visit the buckets in order.
Copy their values back into the original array.
Check that the mapping keeps every value inside a valid bucket.

Expected Strength

With near-uniform data and balanced buckets, distribution and collection are efficient.

Expected: O(n + k)

Worst Case

If most values enter one bucket, sorting that bucket can dominate.

Worst: O(n²) with insertion-sorted buckets

Bucket Sort is often taught for uniformly distributed real values, but range mapping can also be designed for integers.

💻 Complete C Program — Bucket SortView program

This standard classroom version sorts floating-point values in the interval 0 ≤ value < 1.

#include <stdio.h>

#define MAX 100

void insertionSort(float bucket[], int size) {
    for (int i = 1; i < size; i++) {
        float value = bucket[i];
        int j = i - 1;

        while (j >= 0 && bucket[j] > value) {
            bucket[j + 1] = bucket[j];
            j--;
        }
        bucket[j + 1] = value;
    }
}

void bucketSort(float a[], int n) {
    float buckets[MAX][MAX];
    int sizes[MAX] = {0};

    for (int i = 0; i < n; i++) {
        int index = (int)(a[i] * n);
        if (index == n) index = n - 1;
        buckets[index][sizes[index]++] = a[i];
    }

    for (int i = 0; i < n; i++)
        insertionSort(buckets[i], sizes[i]);

    int output = 0;
    for (int i = 0; i < n; i++)
        for (int j = 0; j < sizes[i]; j++)
            a[output++] = buckets[i][j];
}

int main(void) {
    int n;
    float a[MAX];
    scanf("%d", &n);

    if (n < 1 || n > MAX) return 1;
    for (int i = 0; i < n; i++) {
        scanf("%f", &a[i]);
        if (a[i] < 0.0f || a[i] >= 1.0f) return 1;
    }

    bucketSort(a, n);

    for (int i = 0; i < n; i++) printf("%.2f ", a[i]);
    return 0;
}

Sample Input

7
0.42 0.32 0.23 0.52 0.25 0.47 0.51

Sample Output

0.23 0.25 0.32 0.42 0.47 0.51 0.52

ALGORITHM SELECTION

⚖️ 8. Complete Comparison

Algorithm	Best	Average	Worst	Stable	In Place
Merge	n log n	n log n	n log n	Yes	No for arrays
Quick	n log n	n log n	n²	No	Mostly yes
Shell	Gap-dependent	Gap-dependent	Often n² for simple gaps	No	Yes
Counting	n + k	n + k	n + k	Yes*	No
Radix	d(n + b)	d(n + b)	d(n + b)	Yes*	No
Bucket	n + k	n + k expected	n²	Depends	No

*Counting Sort is stable when cumulative positions and right-to-left placement are used; Radix Sort is stable when every digit pass is stable.

C IMPLEMENTATION

💻 10. Quick Sort Using Lomuto Partition

#include <stdio.h>

void swap(int *a, int *b) {
    int temp = *a; *a = *b; *b = temp;
}

int partition(int a[], int low, int high) {
    int pivot = a[high];
    int i = low - 1;
    for (int j = low; j < high; j++) {
        if (a[j] <= pivot) {
            i++;
            swap(&a[i], &a[j]);
        }
    }
    swap(&a[i + 1], &a[high]);
    return i + 1;
}

void quickSort(int a[], int low, int high) {
    if (low < high) {
        int p = partition(a, low, high);
        quickSort(a, low, p - 1);
        quickSort(a, p + 1, high);
    }
}

int main(void) {
    int n; scanf("%d", &n);
    int a[n];
    for (int i = 0; i < n; i++) scanf("%d", &a[i]);
    quickSort(a, 0, n - 1);
    for (int i = 0; i < n; i++) printf("%d ", a[i]);
    return 0;
}

Sample Input

7
8 3 1 7 0 10 2

Sample Output

0 1 2 3 7 8 10

COMBINED C PROGRAM TRACER

🔍 11. Program Tracing — All Advanced Sorting Algorithms

Select an algorithm and enter its values, then click Load Program Tracer. The selected complete C program is loaded into one compact tracer, and its highlighted statement moves as the array and live variables update.

Input Values Algorithm

Use 2–10 comma-separated integers. Bucket Sort uses decimal values from 0 up to, but not including, 1.

Choose the algorithm and values, then click Load Program Tracer. Selection alone does not run the program.

PROGRAM TRACING

💻 C Program

🧠 What is happening?

Press Next to begin.

📊 Live Variables

Array State

Output

—

Step 0 of 0

PERFORMANCE SUMMARY

📈 12. Complexity and Recursion

Situation	Quick Sort Recurrence	Time	Stack
Balanced partitions	T(n)=2T(n/2)+Θ(n)	Θ(n log n)	Θ(log n)
Highly unbalanced	T(n)=T(n−1)+Θ(n)	Θ(n²)	Θ(n)
Randomized expected	Expected balanced progress	O(n log n)	O(log n) expected

Stack optimization: recursively process the smaller partition and loop over the larger one to keep worst-case auxiliary stack usage closer to O(log n).

PRACTICAL DECISIONS

💡 13. Which Sorting Algorithm Should You Choose?

Stable records

Use Merge Sort or a stable Counting/Radix implementation when equal-key order matters.

Fast general array sorting

Use randomized or introspective Quick Sort when cache behavior and low extra memory matter.

Linked lists or external files

Merge Sort suits sequential access and does not require random indexing.

Small integer range

Counting Sort can outperform comparison sorts when k is reasonably small.

Fixed-width integer keys

Radix Sort is useful when the digit count and base are controlled.

Uniform distribution

Bucket Sort works well when values spread evenly across ranges.

AVOID THESE ERRORS

⚠️ 14. Common Mistakes

❌ Wrong recursive bounds

After partition p, recurse on low…p−1 and p+1…high.

❌ Losing stability

Forward placement in Counting Sort may reverse equal records.

❌ Huge count array

Counting Sort wastes memory when key range k is enormous.

❌ Unstable radix pass

Later digit passes cannot repair order destroyed by an unstable earlier pass.

CHECK YOUR UNDERSTANDING

✍️ 15. Practice Problems

Solve each question first. Use Hint only when needed and Show Answer to verify your reasoning.

1. Which advanced sort guarantees O(n log n) in every case?

2. Is standard array Merge Sort in place?

3. Why is Merge Sort useful for linked lists?

4. What is the final position of a Quick Sort pivot after partition?

5. What input can cause O(n²) Quick Sort with the last element as pivot?

6. Why randomize the Quick Sort pivot?

7. Is Quick Sort stable in its common in-place form?

8. What is the final gap used by Shell Sort?

9. Is Shell Sort stable?

10. Give Counting Sort time for n items and key range k.

11. Why is Counting Sort unsuitable when k ≫ n?

12. How can Counting Sort support negative values?

13. Why must each Radix Sort digit pass be stable?

14. Give LSD Radix Sort time with d digits and base b.

15. Under what distribution does Bucket Sort perform well?

16. What causes Bucket Sort’s O(n²) worst case?

17. Which sort is preferred for very large external files?

18. Which studied algorithm is in-place, gap-based and not stable?

19. Can a comparison sort guarantee o(n log n) for arbitrary keys?

20. Choose a sort for stable ordering of one million small-range integer keys.

QUICK RECALL

📝 16. Quick Revision

Comparison sorting has an Ω(n log n) worst-case lower bound.
Merge Sort is stable and always O(n log n), but arrays need O(n) extra space.
Quick Sort is fast and cache-friendly on average, but poor pivots can cause O(n²).
Shell Sort performs gapped insertion passes and ends with gap 1.
Counting Sort is O(n+k) when the integer key range is manageable.
Radix Sort requires a stable digit-level sort.
Bucket Sort depends on balanced value distribution.
Algorithm choice depends on stability, memory, data size, range and distribution.

⚡ Advanced Sorting

🎯 Learning Objectives

🧭 1. How Do We Compare Sorting Algorithms?

Comparison Sort

Non-Comparison Sort

🧩 2. Merge Sort

Divide

Recurse Left

Recurse Right

Merge

🔹 Step-by-Step Algorithm

Guarantee

Trade-off

Sample Input

Sample Output

⚡ 3. Quick Sort

🔹 Step-by-Step Algorithm

🪜 4. Shell Sort

🔹 Step-by-Step Algorithm

Why It Helps

Limitation

Sample Input

Sample Output

🔢 5. Counting Sort

Find Range

Count

Accumulate

Place

🔹 Step-by-Step Algorithm

Sample Input

Sample Output

🧮 6. Radix Sort

🔹 Step-by-Step Algorithm

Time

Requirements

Sample Input

Sample Output

🪣 7. Bucket Sort

🔹 Step-by-Step Algorithm

Expected Strength

Worst Case

Sample Input

Sample Output

⚖️ 8. Complete Comparison

🎬 9. Premium Advanced Sorting Visualizer

📊 Live Array State

💻 10. Quick Sort Using Lomuto Partition

Sample Input

Sample Output

🔍 11. Program Tracing — All Advanced Sorting Algorithms

💻 C Program

🧠 What is happening?

📊 Live Variables

Array State

Output

📈 12. Complexity and Recursion

💡 13. Which Sorting Algorithm Should You Choose?

Stable records

Fast general array sorting

Linked lists or external files

Small integer range

Fixed-width integer keys

Uniform distribution

⚠️ 14. Common Mistakes

❌ Wrong recursive bounds

❌ Losing stability

❌ Huge count array

❌ Unstable radix pass

✍️ 15. Practice Problems

1. Which advanced sort guarantees O(n log n) in every case?

2. Is standard array Merge Sort in place?

3. Why is Merge Sort useful for linked lists?

4. What is the final position of a Quick Sort pivot after partition?

5. What input can cause O(n²) Quick Sort with the last element as pivot?

6. Why randomize the Quick Sort pivot?

7. Is Quick Sort stable in its common in-place form?

8. What is the final gap used by Shell Sort?

9. Is Shell Sort stable?

10. Give Counting Sort time for n items and key range k.

11. Why is Counting Sort unsuitable when k ≫ n?