Ankit Kashyap

Sorting FTW

Sorting algorithms can be broadly classified into two categories:

  1. Comparison-Based Sorting → These algorithms sort elements by comparing them (e.g., Quick Sort, Merge Sort, Heap Sort).
  2. Non-Comparison Sorting → These algorithms do not compare elements directly. Instead, they use properties like the digit structure of numbers or frequency counts.

Stable vs Non-stable

A stable sorting algorithm maintains the relative order of equal elements in the sorted output.

✅ Stable Sorting → If two elements have the same value, their original order is preserved in the sorted result.

❌ Unstable Sorting → The original order of equal elements may change.

Use a stable sort when:

  • Sorting objects where a second sorting criterion is needed (e.g., sorting by last name, then by first name).
  • Sorting lists that were already partially sorted and you want to maintain order.

Key Sorting algos

Sorting AlgorithmStable?TypeTime Complexity (Best / Avg / Worst)Space ComplexityIn-Place?
Merge Sort✅ YesComparisonO(n log n) / O(n log n) / O(n log n)O(n)❌ No
Quick Sort❌ NoComparisonO(n log n) / O(n log n) / O(n²) - if arr is already sortedO(log n) (due to recursion)✅ Yes
Heap Sort❌ NoComparisonO(n log n) / O(n log n) / O(n log n)O(1)✅ Yes
Bubble Sort✅ YesComparisonO(n) / O(n²) / O(n²)O(1)✅ Yes
Insertion Sort✅ YesComparisonO(n) / O(n²) / O(n²)O(1)✅ Yes
Counting Sort✅ YesNon-ComparisonO(n + k) / O(n + k) / O(n + k)O(k)❌ No
Radix Sort✅ YesNon-ComparisonO(nk) / O(nk) / O(nk)O(n + k)❌ No

💡 Key Observations

✔️ In-Place Sorting (✅ Yes): Uses O(1) or O(log n) extra space, modifying the original array (Quick Sort, Heap Sort, Bubble Sort, Insertion Sort).
✔️ Not In-Place (❌ No): Requires additional memory for merging or auxiliary structures (Merge Sort, Counting Sort, Radix Sort).
✔️ Merge Sort is stable but not in-place because it requires extra space for merging.
✔️ Quick Sort is in-place but not stable because swapping elements may change their relative order.
✔️ Counting and Radix Sort are stable but not in-place since they use extra memory to sort.

Further Notes

For FAANG interviews, you should focus on the following sorting algorithms, categorized by importance:

🔥 Must-Know Sorting Algorithms (Used Frequently in Interviews)

1️⃣ Quick Sort (Divide and Conquer)

  • Time Complexity: O(n log n) average, O(n²) worst-case (when poorly partitioned)
  • Space Complexity: O(log n) (due to recursive calls)
  • Best for: General-purpose sorting, often used in practical applications.
  • Key Concept: Picks a pivot, partitions elements around it, and recursively sorts.

2️⃣ Merge Sort (Divide and Conquer)

  • Time Complexity: O(n log n) (always)
  • Space Complexity: O(n)
  • Best for: Sorting linked lists, stable sorting needs.
  • Key Concept: Splits array into halves, sorts them, then merges them.

3️⃣ Heap Sort (Priority Queue-Based Sorting)

  • Time Complexity: O(n log n) (always)
  • Space Complexity: O(1) (in-place sorting)
  • Best for: Situations requiring O(1) extra space with guaranteed O(n log n) sorting.
  • Key Concept: Uses a binary heap to sort elements by repeatedly extracting min/max.

⚡ Important to Know (Less Common in Interviews but Useful)

4️⃣ Counting Sort (Non-Comparison Based)

  • Time Complexity: O(n + k) (where k = range of numbers)
  • Space Complexity: O(k)
  • Best for: Small integer ranges (e.g., sorting ages, exam scores).
  • Key Concept: Uses frequency counting instead of comparisons.

5️⃣ Radix Sort (Non-Comparison Based)

  • Time Complexity: O(nk) (where k = number of digits in the max number)
  • Space Complexity: O(n + k)
  • Best for: Sorting large numbers efficiently.
  • Key Concept: Sorts numbers digit by digit using Counting Sort as a subroutine.

🎯 Basic Sorting Algorithms (Not Used in Interviews but Good for Understanding Basics)

6️⃣ Bubble Sort

  • Time Complexity: O(n²)
  • Space Complexity: O(1)
  • Best for: Teaching sorting but not used in practice.
  • Key Concept: Repeatedly swaps adjacent elements if they are in the wrong order.

7️⃣ Selection Sort

  • Time Complexity: O(n²)
  • Space Complexity: O(1)
  • Best for: Small datasets, theoretical understanding.
  • Key Concept: Selects the smallest element and places it at the beginning.

8️⃣ Insertion Sort

  • Time Complexity: O(n²) (O(n) for nearly sorted input)
  • Space Complexity: O(1)
  • Best for: Small datasets, nearly sorted lists.
  • Key Concept: Builds sorted order one element at a time by inserting in the right position.

📌 Which Sorting Algorithms Should You Master for Interviews?

  1. Quick Sort 🏆 (Most commonly asked in interviews)
  2. Merge Sort 💡 (Guaranteed O(n log n), useful in recursion-based problems)
  3. Heap Sort ⚙️ (Efficient in-place sorting)
  4. Counting Sort & Radix Sort 🚀 (For non-comparison sorting problems)

JavaScript and sorting algo

In JavaScript (specifically in V8, which powers Node.js and Chrome), the built-in .sort() method uses different sorting algorithms based on the data type and length of the array:

  1. TimSort (a hybrid of Merge Sort and Insertion Sort)
    • Used for arrays of numbers and strings in most cases.
    • TimSort is optimized for partially sorted data, making it efficient in real-world scenarios.
  2. Insertion Sort
    • Used for small arrays (length ≤ 10) because it has low overhead and is fast for small datasets.

How it works in V8:

  • For small arrays (<= 10 elements), Insertion Sort is used because of its simplicity and low overhead.
  • For larger arrays, TimSort is used, which adapts to the structure of the data to improve efficiency.

Time Complexity:

  • Best Case (already sorted data): O(n)
  • Average Case: O(n log n)
  • Worst Case: O(n log n)

Learning

Recursive and D&C