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

Mental Model

Sorting can be done by comparing items 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 bins (non-comparison based).

Unsorted array: [4, 2, 7, 1, 3]

Comparison based: compare pairs and swap -> [1, 2, 3, 4, 7]

Non comparison based: use value positions -> [1, 2, 3, 4, 7]

Dry Run Walkthrough

Input: array: [4, 2, 7, 1, 3]

Goal: Sort the array in ascending order using both comparison based and non comparison based methods

Step 1: Start comparison based sort (Bubble Sort): compare 4 and 2, swap because 4 > 2

[2, 4, 7, 1, 3]

Why: We swap to move smaller elements forward

Step 2: Compare 4 and 7, no swap because 4 < 7

[2, 4, 7, 1, 3]

Why: No swap needed if order is correct

Step 3: Compare 7 and 1, swap because 7 > 1

[2, 4, 1, 7, 3]

Why: Move smaller element forward

Step 4: Compare 7 and 3, swap because 7 > 3

[2, 4, 1, 3, 7]

Why: Move smaller element forward

Step 5: Repeat passes until fully sorted: final sorted array is [1, 2, 3, 4, 7]

[1, 2, 3, 4, 7]

Why: Multiple passes ensure all elements are in order

Step 6: Start non comparison based sort (Counting Sort): count occurrences of each number

Counts: {1:1, 2:1, 3:1, 4:1, 7:1}

Why: Counting sort uses counts to place elements directly

Step 7: Use counts to place elements in order: output array becomes [1, 2, 3, 4, 7]

[1, 2, 3, 4, 7]

Why: Direct placement avoids comparisons

Result:

Final sorted array by both methods: [1, 2, 3, 4, 7]

Annotated Code

DSA Python

class SortingComparison:
    def bubble_sort(self, arr):
        n = len(arr)
        for i in range(n):
            for j in range(0, n - i - 1):
                if arr[j] > arr[j + 1]:
                    arr[j], arr[j + 1] = arr[j + 1], arr[j]  # swap to move smaller forward
        return arr

    def counting_sort(self, arr):
        if not arr:
            return arr
        max_val = max(arr)
        count = [0] * (max_val + 1)
        for num in arr:
            count[num] += 1  # count occurrences
        sorted_arr = []
        for num, freq in enumerate(count):
            sorted_arr.extend([num] * freq)  # place elements by count
        return sorted_arr


if __name__ == '__main__':
    arr = [4, 2, 7, 1, 3]
    sorter = SortingComparison()
    sorted_by_comparison = sorter.bubble_sort(arr.copy())
    sorted_by_non_comparison = sorter.counting_sort(arr.copy())
    print('Comparison based sort:', ' -> '.join(map(str, sorted_by_comparison)) + ' -> null')
    print('Non comparison based sort:', ' -> '.join(map(str, sorted_by_non_comparison)) + ' -> null')

if arr[j] > arr[j + 1]: arr[j], arr[j + 1] = arr[j + 1], arr[j] # swap to move smaller forward

swap adjacent elements if out of order to bubble smaller elements forward

for num in arr: count[num] += 1 # count occurrences

count how many times each number appears

for num, freq in enumerate(count): sorted_arr.extend([num] * freq) # place elements by count

build sorted array by placing each number freq times

Output

Comparison based sort: 1 -> 2 -> 3 -> 4 -> 7 -> null

Non comparison based sort: 1 -> 2 -> 3 -> 4 -> 7 -> 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 the range of input values

Space: O(1) extra space for comparison based (in-place swaps); O(k) extra space for counting sort to store counts

vs Alternative: Comparison based sorts are general and work on any data but slower; non comparison based sorts are faster but only work when input values are integers in a limited range

Edge Cases

empty array

returns empty array without error

DSA Python

if not arr:
    return arr

array with one element

returns the same single element array

DSA Python

for i in range(n):  # bubble sort handles single element by no swaps

array with duplicate elements

sorts correctly including duplicates

DSA Python

count[num] += 1  # counting duplicates correctly

When to Use This Pattern

When you see sorting problems with numeric ranges or need faster than O(n log n) sorting, consider non comparison based sorting; otherwise, use comparison based sorting for general data.

Common Mistakes

Mistake: Trying to use counting sort on data with large or unknown ranges causing high memory use
Fix: Use comparison based sorting or limit counting sort to small known ranges

Mistake: Assuming comparison based sorts are always slower without considering input size
Fix: Remember comparison based sorts work on any data type and are simpler for small inputs

Summary

Comparison based sorting uses element comparisons to order data; non comparison based sorting uses element values directly.

Use comparison based sorting for general data and non comparison based sorting for integers in limited ranges for faster performance.

The key insight is that non comparison based sorting avoids pairwise comparisons by using counts or positions based on values.

Practice

1. Which of the following sorting algorithms is not based on comparing elements?

easy

A. Quick Sort

B. Merge Sort

C. Counting Sort

D. Heap Sort

Solution

1. Step 1: Understand comparison based sorting

   Comparison based sorting algorithms decide order by comparing elements pairwise, 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: Counting Sort uses counts, no element comparisons [OK]

Common Mistakes:

• Confusing Counting Sort with Quick Sort
• Thinking Merge Sort is non-comparison based
• Assuming Heap Sort doesn't compare elements

2. Which of the following is the correct syntax to call a non-comparison based sorting function counting_sort(arr) in Python?

easy

A. counting_sort(arr)

B. counting_sort arr

C. counting_sort{arr}

D. counting_sort[arr]

Solution

1. Step 1: Recall Python function call syntax

   Functions are called with parentheses enclosing arguments, like func(args).

2. Step 2: Match syntax with options

   Only counting_sort(arr) uses correct parentheses syntax.

3. Final Answer:

   counting_sort(arr) -> Option A

4. Quick Check:

   Function call uses parentheses [OK]

Hint: Use parentheses () to call functions in Python [OK]

Common Mistakes:

• Using square brackets instead of parentheses
• Omitting parentheses when calling functions
• Using curly braces which are invalid for calls

3. What will be the output of the following Python code using Counting Sort on the array [4, 2, 2, 8, 3, 3, 1]?

def counting_sort(arr):
    max_val = max(arr)
    count = [0] * (max_val + 1)
    for num in arr:
        count[num] += 1
    sorted_arr = []
    for i in range(len(count)):
        sorted_arr.extend([i] * count[i])
    return sorted_arr

print(counting_sort([4, 2, 2, 8, 3, 3, 1]))

medium

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

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

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

D. [4, 2, 2, 8, 3, 3, 1]

Solution

1. Step 1: Count frequencies of each number

   Count array will have counts: 1->1, 2->2, 3->2, 4->1, 8->1, others 0.

2. Step 2: Build sorted array by repeating each number count times

   Sorted array is [1, 2, 2, 3, 3, 4, 8].

3. Final Answer:

   [1, 2, 2, 3, 3, 4, 8] -> Option A

4. Quick Check:

   Counting Sort output = sorted array [OK]

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

Common Mistakes:

• Confusing original array with sorted output
• Reversing the sorted order
• Missing duplicates in output

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

def counting_sort(arr):
    max_val = max(arr)
    count = [0] * max_val
    for num in arr:
        count[num] += 1
    sorted_arr = []
    for i in range(len(count)):
        sorted_arr.extend([i] * count[i])
    return sorted_arr

print(counting_sort([1, 4, 1, 2, 7, 5]))

medium

A. Using extend instead of append causes error

B. count array size is too small, missing last element count

C. max_val should be min_val

D. Loop range should be over arr, not count

Solution

1. Step 1: Check count array size

   Count array size is max_val, but should be max_val + 1 to include max element index.

2. Step 2: Identify impact of size error

   Missing last index causes IndexError or missing counts for max element.

3. Final Answer:

   count array size is too small, missing last element count -> Option B

4. Quick Check:

   Count array size = max_val + 1 needed [OK]

Hint: Count array must cover all values including max [OK]

Common Mistakes:

• Ignoring off-by-one error in count array size
• Thinking extend causes error
• Confusing max_val with min_val

5. You have a large list of integers ranging from 0 to 1000. Which sorting algorithm is best to sort this list efficiently and why? A) Quick Sort because it has average O(n log n) time B) Counting Sort because it sorts in O(n + k) time where k is max value C) Merge Sort because it is stable and always O(n log n) D) Bubble Sort because it is simple to implement

hard

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

B. Bubble Sort because it is simple to implement

C. Merge Sort because it is stable and always O(n log n)

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

Solution

1. Step 1: Analyze input range and size

   Input values are integers from 0 to 1000, so k = 1000 is small compared to n (large list).

2. Step 2: Choose sorting algorithm based on time complexity

   Counting Sort runs in O(n + k), which is efficient for small k and large n, better than O(n log n).

3. Final Answer:

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

4. Quick Check:

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

Hint: Use Counting Sort for small range large list [OK]

Common Mistakes:

• Choosing Quick Sort ignoring input range
• Preferring Bubble Sort despite poor performance
• Ignoring Counting Sort's linear time advantage