Comparison Based vs Non Comparison Based Sorting in DSA Typescript - 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 directly into bins (non comparison based).

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

Non Comparison Based:
Bins: [ ] [1] [3] [5] [ ] [ ] [ ] [ ] [ ] [8]
Values placed directly into bins based on digits or keys.

Dry Run Walkthrough

Input: list: [5, 3, 8, 1], sort ascending

Goal: Show how comparison based sorting and non comparison based sorting organize the list differently

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: Keep elements in order by comparing neighbors

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

[3] -> [5] -> [1] -> [8] -> null

Why: Smaller elements move forward by swapping

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

Bins: [ ] [1] [3] [5] [ ] [ ] [ ] [ ] [ ] [8]

Why: Use element values directly to sort without comparing

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

[1] -> [3] -> [5] -> [8] -> null

Why: Sorted list formed by reading bins in order

Result:

Comparison based final: [1] -> [3] -> [5] -> [8] -> null
Non comparison based final: [1] -> [3] -> [5] -> [8] -> null

Annotated Code

DSA Typescript

class Node {
  value: number;
  next: Node | null;
  constructor(value: number) {
    this.value = value;
    this.next = null;
  }
}

class LinkedList {
  head: Node | null;
  constructor(arr: number[]) {
    this.head = null;
    let current: Node | null = null;
    for (const val of arr) {
      const node = new Node(val);
      if (!this.head) {
        this.head = node;
        current = node;
      } else {
        if (current) current.next = node;
        current = node;
      }
    }
  }

  toArray(): number[] {
    const result: number[] = [];
    let curr = this.head;
    while (curr) {
      result.push(curr.value);
      curr = curr.next;
    }
    return result;
  }

  print(): void {
    let curr = this.head;
    let output = '';
    while (curr) {
      output += curr.value + ' -> ';
      curr = curr.next;
    }
    output += 'null';
    console.log(output);
  }

  bubbleSort(): void {
    if (!this.head) return;
    let swapped: boolean;
    do {
      swapped = false;
      let curr = this.head;
      while (curr && curr.next) {
        if (curr.value > curr.next.value) {
          const temp = curr.value;
          curr.value = curr.next.value;
          curr.next.value = temp;
          swapped = true;
        }
        curr = curr.next;
      }
    } while (swapped);
  }
}

function countingSort(arr: number[]): number[] {
  if (arr.length === 0) return arr;
  const max = Math.max(...arr);
  const count = new Array(max + 1).fill(0);
  for (const num of arr) {
    count[num]++;
  }
  const sorted: number[] = [];
  for (let i = 0; i < count.length; i++) {
    while (count[i] > 0) {
      sorted.push(i);
      count[i]--;
    }
  }
  return sorted;
}

// Driver code
const inputArr = [5, 3, 8, 1];
const list = new LinkedList(inputArr);
console.log('Original list:');
list.print();

console.log('Comparison based sort (Bubble Sort):');
list.bubbleSort();
list.print();

console.log('Non comparison based sort (Counting Sort):');
const sortedArr = countingSort(inputArr);
console.log(sortedArr.join(' -> ') + ' -> null');

while (curr && curr.next) { if (curr.value > curr.next.value) { swap values; swapped = true; } curr = curr.next; }

compare adjacent nodes and swap if out of order to bubble largest to end

do { ... } while (swapped);

repeat passes until no swaps to ensure full sorting

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

count frequency of each value to place directly

for (let i = 0; i < count.length; i++) { while (count[i] > 0) { sorted.push(i); count[i]--; } }

rebuild sorted array by reading counts in order

Output

Original list:

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

Comparison based sort (Bubble Sort):

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

Non comparison based sort (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 max value

Space: O(1) extra space for bubble sort as it sorts in place; O(k) extra space for counting sort to hold counts

vs Alternative: Comparison based sorts work on any data but can be slower; non comparison based sorts are faster but need value constraints (like integers in a range)

Edge Cases

empty list

no sorting needed, returns empty or unchanged

DSA Typescript

if (!this.head) return;

list with one element

already sorted, no swaps occur

DSA Typescript

while (curr && curr.next) { ... }

counting sort with negative numbers

does not handle negatives, may cause error or incorrect results

DSA Typescript

const max = Math.max(...arr); // assumes non-negative

When to Use This Pattern

When you see sorting problems with numeric keys or limited ranges, consider non comparison based sorting for faster results; otherwise, use comparison based sorting for general data.

Common Mistakes

Mistake: Trying to use counting sort on negative or non-integer data
Fix: Use comparison based sorting or adapt counting sort to handle negatives carefully

Mistake: Not repeating passes in bubble sort until no swaps
Fix: Use a loop that continues until a full pass with no swaps occurs

Summary

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

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

The key insight is that comparison based sorts rely on pairwise comparisons, while non comparison based sorts leverage direct indexing or counting.

Practice

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

easy

A. Heap Sort

B. Merge Sort

C. Quick Sort

D. Counting 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 D

4. Quick Check:

   Counting Sort = Non-comparison based [OK]

Hint: Counting Sort uses counts, no direct comparisons [OK]

Common Mistakes:

• Confusing Quick Sort as non-comparison
• Thinking Heap Sort is non-comparison
• Assuming Merge Sort is non-comparison

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

easy

A. countingSort(arr);

B. countingSort arr;

C. countingSort->arr();

D. countingSort[arr];

Solution

1. Step 1: Recall function call syntax in TypeScript

   Functions are called with parentheses and arguments inside, like func(args);.

2. Step 2: Match syntax with options

   Only countingSort(arr); uses correct syntax: countingSort(arr);

3. Final Answer:

   countingSort(arr); -> Option A

4. Quick Check:

   Function call syntax = countingSort(arr); [OK]

Hint: Use parentheses for function calls in TypeScript [OK]

Common Mistakes:

• Omitting parentheses in function call
• Using arrow or brackets incorrectly
• Confusing array access with function call

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

function countingSort(arr: number[]): number[] {
  const max = Math.max(...arr);
  const count = new Array(max + 1).fill(0);
  for (const num of arr) count[num]++;
  let sortedIndex = 0;
  for (let i = 0; i <= max; i++) {
    while (count[i] > 0) {
      arr[sortedIndex++] = i;
      count[i]--;
    }
  }
  return arr;
}

console.log(countingSort([4, 2, 2, 8, 3, 3, 1]));

medium

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

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

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

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

Solution

1. Step 1: Count frequencies of each number

   Count array: index 1=1, 2=2, 3=2, 4=1, 8=1, others=0.

2. Step 2: Rebuild array in sorted order

   Place numbers in order: 1 once, 2 twice, 3 twice, 4 once, 8 once.

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:

• Confusing original order with sorted order
• Miscounting frequencies
• Mixing up indices in count array

4. Identify the error in this Counting Sort implementation snippet:

function countingSort(arr: number[]): number[] {
  const max = Math.max(...arr);
  const count = new Array(max).fill(0);
  for (const num of arr) count[num]++;
  // rest of code omitted
}

medium

A. Array size for count should be max + 1

B. Using Math.max instead of Math.min

C. Missing return statement

D. Using for...of loop incorrectly

Solution

1. Step 1: Check count array size

   Count array size must be max + 1 to include index for max value.

2. Step 2: Identify impact of wrong size

   Using size max misses counting the max element, causing errors.

3. Final Answer:

   Array size for count should be max + 1 -> Option A

4. Quick Check:

   Count array size = max + 1 [OK]

Hint: Count array size must cover max element index [OK]

Common Mistakes:

• Setting count array size to max instead of max + 1
• Ignoring off-by-one errors
• Confusing min and max functions

5. You have an array of 1 million integers ranging from 0 to 1000. Which sorting approach is best and why? A) Quick Sort because it is comparison based and fast on average B) Merge Sort because it guarantees O(n log n) time C) Counting Sort because it sorts in O(n + k) time where k is max value D) Heap Sort because it uses a heap data structure

hard

A. Quick Sort because it is comparison based and fast on average

B. Merge Sort because it guarantees O(n log n) time

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

D. Heap Sort because it uses a heap data structure

Solution

1. Step 1: Analyze input size and range

   Array size is 1 million, values range 0 to 1000 (small range).

2. Step 2: Compare sorting complexities

   Counting Sort runs in O(n + k), here k=1000, much smaller than n, so very efficient.

3. Step 3: Compare with comparison based sorts

   Quick Sort and Merge Sort run in O(n log n), slower for large n compared to Counting Sort here.

4. Final Answer:

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

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 value range
• Ignoring Counting Sort's linear time advantage
• Assuming Heap Sort is always best