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.