Comparison Based vs Non Comparison Based Sorting in DSA Javascript - 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) versus sorting mail by zip codes using bins (non-comparison).

Array: [4, 2, 7, 1, 3]
Comparison sort: compare pairs -> swap if needed
Non-comparison sort: place each number in a bucket based on value

Dry Run Walkthrough

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

Goal: Show how comparison based and non comparison based sorting organize the array

Step 1: Comparison sort compares 4 and 2, swaps because 4 > 2

[2, 4, 7, 1, 3]

Why: We need to order elements by comparing pairs

Step 2: Comparison sort compares 4 and 7, no swap needed

[2, 4, 7, 1, 3]

Why: 4 is less than 7, so order is correct

Step 3: Comparison sort compares 7 and 1, swaps because 7 > 1

[2, 4, 1, 7, 3]

Why: 7 is bigger than 1, so swap to move smaller number forward

Step 4: Non-comparison sort places 1 in bucket 1

Buckets: 1:[1], 2:[], 3:[], 4:[], 7:[]

Why: Directly use value to place element

Step 5: Non-comparison sort places 2 in bucket 2

Buckets: 1:[1], 2:[2], 3:[], 4:[], 7:[]

Why: Each number goes to its own bucket

Step 6: Non-comparison sort places 3, 4, 7 in their buckets

Buckets: 1:[1], 2:[2], 3:[3], 4:[4], 7:[7]

Why: All elements sorted by direct placement

Step 7: Non-comparison sort collects buckets in order

[1, 2, 3, 4, 7]

Why: Concatenate buckets to get sorted array

Result:

Comparison sort final: [1, 2, 3, 4, 7]
Non-comparison sort final: [1, 2, 3, 4, 7]

Annotated Code

DSA Javascript

class ComparisonSort {
  static bubbleSort(arr) {
    let n = arr.length;
    for (let i = 0; i < n - 1; i++) {
      for (let j = 0; j < n - i - 1; j++) {
        if (arr[j] > arr[j + 1]) {
          // swap arr[j] and arr[j+1]
          [arr[j], arr[j + 1]] = [arr[j + 1], arr[j]];
        }
      }
    }
    return arr;
  }
}

class NonComparisonSort {
  static countingSort(arr, maxVal) {
    let count = new Array(maxVal + 1).fill(0);
    for (let num of arr) {
      count[num]++;
    }
    let sorted = [];
    for (let i = 0; i <= maxVal; i++) {
      while (count[i] > 0) {
        sorted.push(i);
        count[i]--;
      }
    }
    return sorted;
  }
}

const input = [4, 2, 7, 1, 3];
const sortedComparison = ComparisonSort.bubbleSort([...input]);
const sortedNonComparison = NonComparisonSort.countingSort([...input], 7);

console.log('Comparison sort final:', sortedComparison.join(', '));
console.log('Non-comparison sort final:', sortedNonComparison.join(', '));

if (arr[j] > arr[j + 1]) { [arr[j], arr[j + 1]] = [arr[j + 1], arr[j]]; }

compare adjacent elements and swap if out of order

for (let num of arr) { count[num]++; }

count frequency of each number using direct indexing

while (count[i] > 0) { sorted.push(i); count[i]--; }

append each number count[i] times to sorted array

Output

Comparison sort final: 1, 2, 3, 4, 7

Non-comparison sort final: 1, 2, 3, 4, 7

Complexity Analysis

Time: O(n^2) for comparison sort because it compares pairs repeatedly; O(n + k) for non-comparison sort where k is max value

Space: O(1) extra space for comparison sort; O(k) extra space for non-comparison sort due to counting array

vs Alternative: Comparison sorts work on any data but can be slower; non-comparison sorts are faster but need limited value ranges

Edge Cases

empty array

returns empty array immediately

DSA Javascript

for (let i = 0; i < n - 1; i++) {

array with one element

returns the same single element array

DSA Javascript

for (let i = 0; i < n - 1; i++) {

array with duplicate values

sorts correctly including duplicates

DSA Javascript

count[num]++;

When to Use This Pattern

When sorting numbers with a known small range, consider non-comparison sorting for speed; otherwise, use comparison sorting for general data.

Common Mistakes

Mistake: Trying non-comparison sort on data with large or unknown range
Fix: Use comparison sort or limit input range before non-comparison sort

Mistake: Not swapping elements correctly in comparison sort
Fix: Use a proper swap method or destructuring assignment

Summary

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

Use comparison sorting for general data and non-comparison sorting when values are integers in a small range.

The key insight is that non-comparison sorting can be faster by avoiding comparisons but only works with limited value types.