Sorting Algorithms

Sorting is one of the most fundamental operations in computer science. Understanding different sorting algorithms and their trade-offs is essential for coding interviews and efficient programming.

---

Why This Matters in Interviews

Sorting algorithms are frequently tested because they demonstrate:

• Algorithm design skills: Understanding divide-and-conquer, greedy approaches
• Complexity analysis: Time and space complexity trade-offs
• Problem-solving: Many problems can be solved by sorting first
• System design: Choosing appropriate sorting for different scenarios

Interviewers use sorting problems to assess your understanding of fundamental algorithms and your ability to optimize solutions.

---

Core Concepts

• Comparison-based sorting: Algorithms that compare elements (merge, quick, heap)
• Non-comparison sorting: Algorithms using other properties (counting, radix, bucket)
• Stable sorting: Maintains relative order of equal elements
• In-place sorting: Uses O(1) extra space
• Adaptive sorting: Performs better on partially sorted data
• Time complexity: Best, average, and worst case scenarios
• Space complexity: Auxiliary space requirements

---

Detailed Explanation

Comparison-Based Sorting

1. Bubble Sort:

function bubbleSort(arr: number[]): void {
  const n = arr.length;
  
  for (let i = 0; i < n - 1; i++) {
    let swapped = false;
    
    for (let j = 0; j < n - i - 1; j++) {
      if (arr[j] > arr[j + 1]) {
        [arr[j], arr[j + 1]] = [arr[j + 1], arr[j]];
        swapped = true;
      }
    }
    
    // Optimization: stop if no swaps
    if (!swapped) break;
  }
}

// Time: O(n²) worst/average, O(n) best (adaptive)
// Space: O(1)
// Stable: Yes

2. Insertion Sort:

function insertionSort(arr: number[]): void {
  for (let i = 1; i < arr.length; i++) {
    const key = arr[i];
    let j = i - 1;
    
    while (j >= 0 && arr[j] > key) {
      arr[j + 1] = arr[j];
      j--;
    }
    
    arr[j + 1] = key;
  }
}

// Time: O(n²) worst/average, O(n) best (adaptive)
// Space: O(1)
// Stable: Yes
// Good for: Small arrays, nearly sorted data

3. Selection Sort:

function selectionSort(arr: number[]): void {
  const n = arr.length;
  
  for (let i = 0; i < n - 1; i++) {
    let minIdx = i;
    
    for (let j = i + 1; j < n; j++) {
      if (arr[j] < arr[minIdx]) {
        minIdx = j;
      }
    }
    
    [arr[i], arr[minIdx]] = [arr[minIdx], arr[i]];
  }
}

// Time: O(n²) always
// Space: O(1)
// Stable: No

4. Merge Sort:

function mergeSort(arr: number[]): number[] {
  if (arr.length <= 1) return arr;
  
  const mid = Math.floor(arr.length / 2);
  const left = mergeSort(arr.slice(0, mid));
  const right = mergeSort(arr.slice(mid));
  
  return merge(left, right);
}

function merge(left: number[], right: number[]): number[] {
  const result: number[] = [];
  let i = 0, j = 0;
  
  while (i < left.length && j < right.length) {
    if (left[i] <= right[j]) {
      result.push(left[i++]);
    } else {
      result.push(right[j++]);
    }
  }
  
  return result.concat(left.slice(i)).concat(right.slice(j));
}

// Time: O(n log n) always
// Space: O(n)
// Stable: Yes
// Good for: Large datasets, external sorting, stable sort needed

5. Quick Sort:

function quickSort(arr: number[], low: number = 0, high: number = arr.length - 1): void {
  if (low < high) {
    const pi = partition(arr, low, high);
    quickSort(arr, low, pi - 1);
    quickSort(arr, pi + 1, high);
  }
}

function partition(arr: number[], low: number, high: number): number {
  const pivot = arr[high];
  let i = low - 1;
  
  for (let j = low; j < high; j++) {
    if (arr[j] < pivot) {
      i++;
      [arr[i], arr[j]] = [arr[j], arr[i]];
    }
  }
  
  [arr[i + 1], arr[high]] = [arr[high], arr[i + 1]];
  return i + 1;
}

// Time: O(n log n) average, O(n²) worst
// Space: O(log n) average (recursion stack)
// Stable: No (can be made stable with extra space)
// Good for: General-purpose sorting, in-place needed

6. Heap Sort:

function heapSort(arr: number[]): void {
  const n = arr.length;
  
  // Build max heap
  for (let i = Math.floor(n / 2) - 1; i >= 0; i--) {
    heapify(arr, n, i);
  }
  
  // Extract elements one by one
  for (let i = n - 1; i > 0; i--) {
    [arr[0], arr[i]] = [arr[i], arr[0]];
    heapify(arr, i, 0);
  }
}

function heapify(arr: number[], n: number, i: number): void {
  let largest = i;
  const left = 2 * i + 1;
  const right = 2 * i + 2;
  
  if (left < n && arr[left] > arr[largest]) {
    largest = left;
  }
  
  if (right < n && arr[right] > arr[largest]) {
    largest = right;
  }
  
  if (largest !== i) {
    [arr[i], arr[largest]] = [arr[largest], arr[i]];
    heapify(arr, n, largest);
  }
}

// Time: O(n log n) always
// Space: O(1)
// Stable: No
// Good for: Guaranteed O(n log n), in-place needed

Non-Comparison Sorting

7. Counting Sort:

function countingSort(arr: number[], max: number): number[] {
  const count = new Array(max + 1).fill(0);
  const output = new Array(arr.length);
  
  // Count occurrences
  for (const num of arr) {
    count[num]++;
  }
  
  // Cumulative count
  for (let i = 1; i <= max; i++) {
    count[i] += count[i - 1];
  }
  
  // Build output array
  for (let i = arr.length - 1; i >= 0; i--) {
    output[count[arr[i]] - 1] = arr[i];
    count[arr[i]]--;
  }
  
  return output;
}

// Time: O(n + k) where k is range
// Space: O(k)
// Stable: Yes
// Good for: Small range of integers

8. Radix Sort:

function radixSort(arr: number[]): void {
  const max = Math.max(...arr);
  
  // Sort by each digit
  for (let exp = 1; Math.floor(max / exp) > 0; exp *= 10) {
    countingSortByDigit(arr, exp);
  }
}

function countingSortByDigit(arr: number[], exp: number): void {
  const output = new Array(arr.length);
  const count = new Array(10).fill(0);
  
  // Count occurrences of current digit
  for (let i = 0; i < arr.length; i++) {
    count[Math.floor(arr[i] / exp) % 10]++;
  }
  
  // Cumulative count
  for (let i = 1; i < 10; i++) {
    count[i] += count[i - 1];
  }
  
  // Build output
  for (let i = arr.length - 1; i >= 0; i--) {
    const digit = Math.floor(arr[i] / exp) % 10;
    output[count[digit] - 1] = arr[i];
    count[digit]--;
  }
  
  // Copy back
  for (let i = 0; i < arr.length; i++) {
    arr[i] = output[i];
  }
}

// Time: O(d * (n + k)) where d is number of digits
// Space: O(n + k)
// Stable: Yes
// Good for: Integers with fixed number of digits

---

Examples

Sorting Custom Objects

interface Person {
  name: string;
  age: number;
}

function sortByAge(people: Person[]): Person[] {
  return people.sort((a, b) => a.age - b.age);
}

function sortByName(people: Person[]): Person[] {
  return people.sort((a, b) => a.name.localeCompare(b.name));
}

// Multi-key sorting
function sortByAgeThenName(people: Person[]): Person[] {
  return people.sort((a, b) => {
    if (a.age !== b.age) {
      return a.age - b.age;
    }
    return a.name.localeCompare(b.name);
  });
}

Finding Kth Largest Element

function findKthLargest(nums: number[], k: number): number {
  // Quick select algorithm
  return quickSelect(nums, 0, nums.length - 1, nums.length - k);
}

function quickSelect(arr: number[], low: number, high: number, k: number): number {
  if (low === high) return arr[low];
  
  const pi = partition(arr, low, high);
  
  if (pi === k) {
    return arr[pi];
  } else if (pi < k) {
    return quickSelect(arr, pi + 1, high, k);
  } else {
    return quickSelect(arr, low, pi - 1, k);
  }
}

// Time: O(n) average, O(n²) worst
// Space: O(1)

---

Common Pitfalls

• Not considering stability: Equal elements may change order. Fix: Use stable sort when order matters
• Worst case complexity: Quick sort can degrade to O(n²). Fix: Use randomized pivot or heap sort
• Space complexity: Merge sort uses O(n) space. Fix: Use in-place sort if space is limited
• Integer overflow: In counting/radix sort with large numbers. Fix: Use appropriate data types
• Custom comparator errors: Wrong comparison logic. Fix: Test with edge cases
• Assuming sorted input: Not handling already sorted arrays efficiently. Fix: Use adaptive algorithms

---

Interview Questions

Beginner

Q: Explain the difference between merge sort and quick sort. When would you use each?

A:

Merge Sort:

• Time: O(n log n) always (best, average, worst)
• Space: O(n) extra space
• Stable: Yes
• Use when: Need guaranteed O(n log n), stability required, external sorting

Quick Sort:

• Time: O(n log n) average, O(n²) worst case
• Space: O(log n) recursion stack
• Stable: No (default implementation)
• Use when: General-purpose sorting, in-place needed, average case performance matters

Key Differences:

Feature	Merge Sort	Quick Sort
Worst case	O(n log n)	O(n²)
Average case	O(n log n)	O(n log n)
Space	O(n)	O(log n)
Stable	Yes	No
In-place	No	Yes

When to use:

• Merge sort: Large datasets, stability needed, worst-case guarantee
• Quick sort: General use, in-place needed, average performance

---

Intermediate

Q: Implement merge sort and analyze its time and space complexity. How would you optimize it?

A:

function mergeSort(arr: number[]): number[] {
  if (arr.length <= 1) return arr;
  
  const mid = Math.floor(arr.length / 2);
  const left = mergeSort(arr.slice(0, mid));
  const right = mergeSort(arr.slice(mid));
  
  return merge(left, right);
}

function merge(left: number[], right: number[]): number[] {
  const result: number[] = [];
  let i = 0, j = 0;
  
  while (i < left.length && j < right.length) {
    if (left[i] <= right[j]) {
      result.push(left[i++]);
    } else {
      result.push(right[j++]);
    }
  }
  
  return result.concat(left.slice(i)).concat(right.slice(j));
}

// Time Complexity: O(n log n)
// - Divide: O(log n) levels
// - Merge at each level: O(n)
// - Total: O(n log n)

// Space Complexity: O(n)
// - Recursion stack: O(log n)
// - Temporary arrays: O(n)
// - Total: O(n)

// Optimizations:
// 1. Use insertion sort for small subarrays (threshold ~10-20)
// 2. Check if already sorted before merging
// 3. Bottom-up iterative version to avoid recursion overhead
// 4. In-place merge (complex, uses O(log n) space)

Optimized version:

const INSERTION_SORT_THRESHOLD = 10;

function optimizedMergeSort(arr: number[]): number[] {
  if (arr.length <= INSERTION_SORT_THRESHOLD) {
    return insertionSort(arr);
  }
  
  const mid = Math.floor(arr.length / 2);
  const left = optimizedMergeSort(arr.slice(0, mid));
  const right = optimizedMergeSort(arr.slice(mid));
  
  // Skip merge if already sorted
  if (left[left.length - 1] <= right[0]) {
    return left.concat(right);
  }
  
  return merge(left, right);
}

---

Senior

Q: Design a sorting system for a distributed environment where data is stored across multiple nodes. How do you handle network latency, node failures, and ensure correctness?

A:

class DistributedSorting {
  private nodes: Node[];
  private coordinator: Coordinator;
  
  constructor(nodes: Node[]) {
    this.nodes = nodes;
    this.coordinator = new Coordinator(nodes);
  }
  
  async sort(data: DistributedData): Promise<SortedData> {
    // Phase 1: Local sorting on each node
    const localSortPromises = this.nodes.map(node => 
      node.localSort(data.getPartition(node.id))
    );
    
    const localSorted = await Promise.all(localSortPromises);
    
    // Phase 2: Merge sorted partitions
    return await this.coordinator.mergeSorted(localSorted);
  }
}

class Node {
  async localSort(partition: number[]): Promise<number[]> {
    // Use efficient local sort (quick sort or merge sort)
    return this.quickSort(partition);
  }
  
  private quickSort(arr: number[]): number[] {
    // Standard quick sort implementation
    if (arr.length <= 1) return arr;
    
    const pivot = arr[Math.floor(arr.length / 2)];
    const left = arr.filter(x => x < pivot);
    const middle = arr.filter(x => x === pivot);
    const right = arr.filter(x => x > pivot);
    
    return [...this.quickSort(left), ...middle, ...this.quickSort(right)];
  }
}

class Coordinator {
  async mergeSorted(sortedPartitions: number[][]): Promise<number[]> {
    // K-way merge using min heap
    const heap = new MinHeap<{ value: number; partitionIndex: number; elementIndex: number }>();
    const result: number[] = [];
    
    // Initialize heap with first element from each partition
    for (let i = 0; i < sortedPartitions.length; i++) {
      if (sortedPartitions[i].length > 0) {
        heap.insert({
          value: sortedPartitions[i][0],
          partitionIndex: i,
          elementIndex: 0
        });
      }
    }
    
    // Merge
    while (!heap.isEmpty()) {
      const min = heap.extractMin()!;
      result.push(min.value);
      
      // Add next element from same partition
      const nextIndex = min.elementIndex + 1;
      if (nextIndex < sortedPartitions[min.partitionIndex].length) {
        heap.insert({
          value: sortedPartitions[min.partitionIndex][nextIndex],
          partitionIndex: min.partitionIndex,
          elementIndex: nextIndex
        });
      }
    }
    
    return result;
  }
  
  async mergeSortedWithFailureHandling(
    sortedPartitions: number[][],
    nodeIds: string[]
  ): Promise<number[]> {
    // Handle node failures
    const activePartitions: number[][] = [];
    
    for (let i = 0; i < sortedPartitions.length; i++) {
      try {
        // Verify partition is accessible
        await this.verifyPartition(nodeIds[i], sortedPartitions[i]);
        activePartitions.push(sortedPartitions[i]);
      } catch (error) {
        // Node failed, use replica
        const replica = await this.getReplica(nodeIds[i]);
        activePartitions.push(replica);
      }
    }
    
    return await this.mergeSorted(activePartitions);
  }
  
  private async verifyPartition(nodeId: string, partition: number[]): Promise<void> {
    // Check if node is responsive
    // Verify partition integrity
  }
  
  private async getReplica(nodeId: string): Promise<number[]> {
    // Get replica from another node
    // Re-sort if needed
  }
}

// Time: O(n log n / p + n log p) where p is number of nodes
// - Local sort: O((n/p) log(n/p)) per node
// - Merge: O(n log p) for k-way merge
// Space: O(n) for result, O(p) for heap

Features:

1. Local sorting: Sort data on each node independently
2. K-way merge: Efficiently merge sorted partitions
3. Failure handling: Use replicas if node fails
4. Load balancing: Distribute data evenly across nodes

---

Key Takeaways

• Comparison-based: Merge sort (stable, guaranteed O(n log n)), Quick sort (in-place, average O(n log n)), Heap sort (guaranteed O(n log n), in-place)
• Non-comparison: Counting sort (small range), Radix sort (fixed digits), Bucket sort (uniform distribution)
• Time complexity: Best O(n log n) for comparison-based, O(n) for non-comparison with constraints
• Space complexity: Merge sort O(n), Quick sort O(log n), Heap sort O(1)
• Stability: Important when relative order of equal elements matters
• When to use: Consider data size, range, stability needs, space constraints
• Optimizations: Hybrid approaches, adaptive algorithms, parallel sorting