Comparison Based vs Non Comparison Based Sorting in DSA C# - Trade-offs & Analysis

Mental Model

Sorting can be done by comparing elements or by using their values directly without comparing.

Analogy: Imagine sorting books by comparing their titles one by one (comparison based) versus sorting mail by zip codes using pigeonholes (non comparison based).

Comparison Based Sorting:
[5] -> [3] -> [8] -> [1] -> null

Non Comparison Based Sorting:
Buckets: [ ] [ ] [ ] [ ] [ ] [ ] [ ] [ ] [ ] [ ]
Values placed directly into buckets based on digits or keys.

Dry Run Walkthrough

Input: list: 5, 3, 8, 1; sort ascending

Goal: Show how comparison based and non comparison based sorting handle the same list

Step 1: Comparison based: compare 5 and 3, swap because 5 > 3

3 -> 5 -> 8 -> 1 -> null

Why: We need to order elements by comparing pairs

Step 2: Comparison based: compare 5 and 8, no swap because 5 < 8

3 -> 5 -> 8 -> 1 -> null

Why: Elements are in correct order here

Step 3: Comparison based: compare 8 and 1, swap because 8 > 1

3 -> 5 -> 1 -> 8 -> null

Why: Keep pushing larger elements to the right

Step 4: Non comparison based: place elements into buckets by value (0-9)

Buckets: [ ] [1] [ ] [3] [ ] [5] [ ] [ ] [ ] [8]

Why: We use element values directly to sort without comparing

Step 5: Non comparison based: collect elements from buckets in order

1 -> 3 -> 5 -> 8 -> null

Why: Gathering sorted elements from buckets gives sorted list

Result:

Sorted list: 1 -> 3 -> 5 -> 8 -> null

Annotated Code

DSA C#

using System;
using System.Collections.Generic;

class SortingComparison
{
    // Comparison based: Bubble Sort
    public static void BubbleSort(int[] arr)
    {
        int n = arr.Length;
        for (int i = 0; i < n - 1; i++)
        {
            for (int j = 0; j < n - i - 1; j++)
            {
                if (arr[j] > arr[j + 1])
                {
                    int temp = arr[j];
                    arr[j] = arr[j + 1];
                    arr[j + 1] = temp;
                }
            }
        }
    }

    // Non comparison based: Counting Sort (for 0-9 range)
    public static void CountingSort(int[] arr)
    {
        int max = 9;
        int[] count = new int[max + 1];
        foreach (int num in arr)
        {
            count[num]++;
        }
        int index = 0;
        for (int i = 0; i <= max; i++)
        {
            while (count[i] > 0)
            {
                arr[index++] = i;
                count[i]--;
            }
        }
    }

    public static void PrintArray(int[] arr)
    {
        for (int i = 0; i < arr.Length; i++)
        {
            Console.Write(arr[i]);
            if (i != arr.Length - 1) Console.Write(" -> ");
        }
        Console.WriteLine(" -> null");
    }

    static void Main()
    {
        int[] arr1 = {5, 3, 8, 1};
        int[] arr2 = {5, 3, 8, 1};

        Console.WriteLine("Comparison Based Sorting (Bubble Sort):");
        BubbleSort(arr1);
        PrintArray(arr1);

        Console.WriteLine("Non Comparison Based Sorting (Counting Sort):");
        CountingSort(arr2);
        PrintArray(arr2);
    }
}

if (arr[j] > arr[j + 1])

compare adjacent elements to decide if swap needed

arr[j] = arr[j + 1]; arr[j + 1] = temp;

swap elements to move larger one right

count[num]++;

count frequency of each element by value

while (count[i] > 0) { arr[index++] = i; count[i]--; }

place elements back in order based on counts

Output

Comparison Based Sorting (Bubble Sort):

1 -> 3 -> 5 -> 8 -> null

Non Comparison Based Sorting (Counting Sort):

1 -> 3 -> 5 -> 8 -> null

Complexity Analysis

Time: O(n^2) for comparison based (bubble sort) because it compares pairs repeatedly; O(n + k) for non comparison based (counting sort) where k is range of values

Space: O(1) extra space for bubble sort; O(k) extra space for counting sort to hold counts

vs Alternative: Comparison based sorts work for any data but are slower; non comparison based sorts are faster but need limited value ranges or special conditions

Edge Cases

empty array

both sorts handle gracefully with no changes

DSA C#

for (int i = 0; i < arr.Length; i++) in PrintArray

array with duplicates

counting sort counts duplicates correctly; bubble sort swaps as needed

DSA C#

count[num]++ in CountingSort

array with values outside 0-9 range for counting sort

counting sort fails or errors because of fixed bucket size

DSA C#

int max = 9; // fixed range in CountingSort

When to Use This Pattern

When sorting integers with a small known range, consider non comparison based sorting for faster performance; otherwise, use comparison based sorting for general data.

Common Mistakes

Mistake: Trying to use counting sort on data with large or unknown range
Fix: Use comparison based sorting or adapt non comparison sort to handle larger ranges

Mistake: Assuming comparison based sorting is always slower without considering data size
Fix: Remember comparison based sorts work for all data types and sizes, sometimes more practical

Summary

Comparison based sorting orders elements by comparing pairs; non comparison based sorting uses element values directly.

Use comparison based sorting for general data and non comparison based sorting for integers with limited range.

The key insight is that non comparison based sorting can be faster but only when data fits certain conditions.

Practice

1. Which of the following sorting algorithms is non-comparison based?

easy

A. Merge Sort

B. Quick Sort

C. Counting Sort

D. Heap Sort

Solution

1. Step 1: Understand comparison based sorting

   Comparison based sorting algorithms decide order by comparing elements, like Merge Sort, Quick Sort, and Heap Sort.

2. Step 2: Identify non-comparison based sorting

   Counting Sort uses counting frequencies and does not compare elements directly.

3. Final Answer:

   Counting Sort -> Option C

4. Quick Check:

   Non-comparison based = Counting Sort [OK]

Hint: Non-comparison sorts use counting or buckets, not element comparisons [OK]

Common Mistakes:

• Confusing Quick Sort as non-comparison
• Thinking Heap Sort is non-comparison
• Assuming all sorts compare elements

2. Which of the following is the correct syntax to call Radix Sort method named RadixSort on an integer array arr in C#?

easy

A. RadixSort(arr);

B. arr.RadixSort();

C. RadixSort<int>(arr);

D. RadixSort arr;

Solution

1. Step 1: Understand method call syntax in C#

   Calling a static method with an array argument uses method name and parentheses with the array inside.

2. Step 2: Analyze options

   RadixSort(arr); uses correct syntax: RadixSort(arr); arr.RadixSort(); tries to call as instance method which is incorrect unless defined so. RadixSort<int>(arr); uses generic syntax unnecessarily. RadixSort arr; is invalid syntax.

3. Final Answer:

   RadixSort(arr); -> Option A

4. Quick Check:

   Static method call = RadixSort(arr); [OK]

Hint: Static method calls use MethodName(args) syntax [OK]

Common Mistakes:

• Using instance method call on array
• Adding unnecessary generic syntax
• Writing invalid declaration instead of call

3. What will be the output of the following C# code snippet?

int[] arr = {4, 2, 2, 8, 3, 3, 1};
CountingSort(arr);
Console.WriteLine(string.Join(", ", arr));

void CountingSort(int[] array) {
    int max = array.Max();
    int[] count = new int[max + 1];
    foreach (int num in array) count[num]++;
    int index = 0;
    for (int i = 0; i <= max; i++) {
        while (count[i] > 0) {
            array[index++] = i;
            count[i]--;
        }
    }
}

medium

A. 8, 4, 3, 3, 2, 2, 1

B. 1, 2, 2, 3, 3, 4, 8

C. 4, 2, 2, 8, 3, 3, 1

D. 1, 1, 2, 2, 3, 3, 4

Solution

1. Step 1: Understand Counting Sort logic

   Counting Sort counts occurrences of each number and then writes them back in sorted order.

2. Step 2: Trace the code with input array

   Input: {4, 2, 2, 8, 3, 3, 1} Count array: counts of 1=1, 2=2, 3=2, 4=1, 8=1 Output array after sorting: 1, 2, 2, 3, 3, 4, 8

3. Final Answer:

   1, 2, 2, 3, 3, 4, 8 -> Option B

4. Quick Check:

   Counting Sort output = sorted array [OK]

Hint: Counting Sort outputs sorted array by frequency count [OK]

Common Mistakes:

• Assuming original array remains unchanged
• Confusing Counting Sort with reverse order
• Miscounting frequencies

4. The following code attempts to implement Radix Sort but has a bug. What is the error?

void RadixSort(int[] arr) {
    int max = arr.Max();
    for (int exp = 1; max / exp > 0; exp *= 10) {
        CountingSortByDigit(arr, exp);
    }
}

void CountingSortByDigit(int[] arr, int exp) {
    int n = arr.Length;
    int[] output = new int[n];
    int[] count = new int[10];

    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--) {
        output[count[(arr[i] / exp) % 10] - 1] = arr[i];
        count[(arr[i] / exp) % 10]--;
    }

    // Missing step here
}

medium

A. The loop for counting prefix sums should start from 0

B. The count array size should be 100 instead of 10

C. The exponent variable exp should be incremented by 1 each iteration

D. The sorted output array is not copied back to the original array

Solution

1. Step 1: Analyze CountingSortByDigit function

   The function builds output array sorted by digit but does not copy output back to arr.

2. Step 2: Identify missing step

   After building output, we must copy output elements back to arr to update it for next digit sorting.

3. Final Answer:

   The sorted output array is not copied back to the original array -> Option D

4. Quick Check:

   Missing copy back step = bug [OK]

Hint: Radix Sort needs copying output back each digit pass [OK]

Common Mistakes:

• Thinking count array size should be larger
• Starting prefix sum loop incorrectly
• Incrementing exp by 1 instead of multiplying by 10

5. You have an array of 1 million integers ranging from 0 to 1000. Which sorting algorithm is the most efficient choice and why?

hard

A. Counting Sort, because it sorts in O(n + k) time where k is max value

B. Heap Sort, because it uses constant extra space

C. Merge Sort, because it is stable and works well on large data

D. Quick Sort, because it has average O(n log n) time

Solution

1. Step 1: Analyze input size and range

   Array size n = 1,000,000; max value k = 1000 (small compared to n).

2. Step 2: Compare algorithm complexities

   Counting Sort runs in O(n + k) which is O(1,001,000) here, faster than O(n log n) for comparison sorts.

3. Step 3: Choose best algorithm

   Counting Sort is efficient for small range large data, so best choice.

4. Final Answer:

   Counting Sort, because it sorts in O(n + k) time where k is max value -> Option A

5. Quick Check:

   Small range + large n = Counting Sort best [OK]

Hint: Use Counting Sort for large arrays with small value range [OK]

Common Mistakes:

• Choosing Quick Sort ignoring small range advantage
• Preferring Merge Sort for speed over Counting Sort
• Ignoring Counting Sort's linear time benefit