SyntaxShelf
DSA

Sorting

Interview Prep · 8 entries

Bubble Sort

syntax
Repeatedly swap adjacent elements if out of order.
After each pass, the largest unsorted element 'bubbles' to its correct position.
example
// JavaScript
function bubbleSort(arr) {
  const n = arr.length;
  for (let i = 0; i < n - 1; i++) {
    let swapped = false;
    for (let j = 0; j < n - 1 - i; j++) {
      if (arr[j] > arr[j + 1]) {
        [arr[j], arr[j + 1]] = [arr[j + 1], arr[j]];
        swapped = true;
      }
    }
    if (!swapped) break; // already sorted
  }
  return arr;
}

# Python
def bubble_sort(arr):
    n = len(arr)
    for i in range(n - 1):
        swapped = False
        for j in range(n - 1 - i):
            if arr[j] > arr[j + 1]:
                arr[j], arr[j + 1] = arr[j + 1], arr[j]
                swapped = True
        if not swapped:
            break
    return arr
output
bubble_sort([5,3,8,1,2]) → [1,2,3,5,8]

Note Time: O(n^2) average/worst, O(n) best (already sorted with early exit). Space: O(1). Stable sort. Never use in production — only know it for interviews. The early termination optimization (swapped flag) is worth mentioning.

bubble sortsorting algorithmadjacent swapstable sort

Selection Sort

syntax
Find the minimum element in the unsorted portion.
Swap it to the front of the unsorted portion.
Repeat.
example
// JavaScript
function selectionSort(arr) {
  for (let i = 0; i < arr.length - 1; i++) {
    let minIdx = i;
    for (let j = i + 1; j < arr.length; j++) {
      if (arr[j] < arr[minIdx]) minIdx = j;
    }
    if (minIdx !== i) {
      [arr[i], arr[minIdx]] = [arr[minIdx], arr[i]];
    }
  }
  return arr;
}

# Python
def selection_sort(arr):
    for i in range(len(arr) - 1):
        min_idx = i
        for j in range(i + 1, len(arr)):
            if arr[j] < arr[min_idx]:
                min_idx = j
        if min_idx != i:
            arr[i], arr[min_idx] = arr[min_idx], arr[i]
    return arr
output
selection_sort([64,25,12,22,11]) → [11,12,22,25,64]

Note Time: O(n^2) all cases. Space: O(1). NOT stable (swapping can change relative order of equal elements). Minimizes the number of swaps (at most n-1), which can matter when writes are expensive.

selection sortfind minimum sortsorting algorithmin-place sort

Insertion Sort

syntax
Build sorted portion from left.
Take next unsorted element, insert it into the correct position in the sorted portion.
example
// JavaScript
function insertionSort(arr) {
  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;
  }
  return arr;
}

# Python
def insertion_sort(arr):
    for i in range(1, len(arr)):
        key = arr[i]
        j = i - 1
        while j >= 0 and arr[j] > key:
            arr[j + 1] = arr[j]
            j -= 1
        arr[j + 1] = key
    return arr
output
insertion_sort([5,2,4,6,1,3]) → [1,2,3,4,5,6]

Note Time: O(n^2) worst/avg, O(n) best (nearly sorted). Space: O(1). Stable. Excellent for small arrays (< ~20 elements) and nearly sorted data. TimSort (Python/Java default) uses insertion sort for small subarrays within merge sort.

insertion sortstable sortnearly sortedsmall array sort

Merge Sort

syntax
Divide array in half, recursively sort each half, merge the sorted halves.
Merge step: two pointers comparing elements from each half.
example
// JavaScript
function mergeSort(arr) {
  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(a, b) {
  const result = [];
  let i = 0, j = 0;
  while (i < a.length && j < b.length) {
    if (a[i] <= b[j]) result.push(a[i++]);
    else result.push(b[j++]);
  }
  return result.concat(a.slice(i), b.slice(j));
}

# Python
def merge_sort(arr):
    if len(arr) <= 1:
        return arr
    mid = len(arr) // 2
    left = merge_sort(arr[:mid])
    right = merge_sort(arr[mid:])
    return merge(left, right)

def merge(a, b):
    result = []
    i = j = 0
    while i < len(a) and j < len(b):
        if a[i] <= b[j]:
            result.append(a[i]); i += 1
        else:
            result.append(b[j]); j += 1
    result.extend(a[i:])
    result.extend(b[j:])
    return result
output
merge_sort([38,27,43,3,9,82,10]) → [3,9,10,27,38,43,82]

Note Time: O(n log n) always. Space: O(n). Stable. Guaranteed O(n log n) regardless of input — unlike quicksort. Preferred for linked lists (no random access needed, O(1) space merge). The merge function is reusable in many problems.

merge sortdivide and conquer sortstable sortguaranteed n log n

Quick Sort

syntax
Pick a pivot. Partition: elements < pivot go left, >= pivot go right.
Recursively sort left and right partitions.
example
// JavaScript
function quickSort(arr, lo = 0, hi = arr.length - 1) {
  if (lo >= hi) return arr;
  const pivotIdx = partition(arr, lo, hi);
  quickSort(arr, lo, pivotIdx - 1);
  quickSort(arr, pivotIdx + 1, hi);
  return arr;
}

function partition(arr, lo, hi) {
  const pivot = arr[hi];
  let i = lo;
  for (let j = lo; j < hi; j++) {
    if (arr[j] < pivot) {
      [arr[i], arr[j]] = [arr[j], arr[i]];
      i++;
    }
  }
  [arr[i], arr[hi]] = [arr[hi], arr[i]];
  return i;
}

# Python
def quick_sort(arr, lo=0, hi=None):
    if hi is None:
        hi = len(arr) - 1
    if lo >= hi:
        return arr
    pivot_idx = partition(arr, lo, hi)
    quick_sort(arr, lo, pivot_idx - 1)
    quick_sort(arr, pivot_idx + 1, hi)
    return arr

def partition(arr, lo, hi):
    pivot = arr[hi]
    i = lo
    for j in range(lo, hi):
        if arr[j] < pivot:
            arr[i], arr[j] = arr[j], arr[i]
            i += 1
    arr[i], arr[hi] = arr[hi], arr[i]
    return i
output
quick_sort([10,7,8,9,1,5]) → [1,5,7,8,9,10]

Note Time: O(n log n) avg, O(n^2) worst (already sorted with bad pivot). Space: O(log n) avg stack. NOT stable. Randomizing the pivot avoids worst case. In practice, quicksort is often faster than merge sort due to cache locality. Lomuto partition (shown) is simpler; Hoare partition is faster.

quick sortpartition sortpivot sortin-place sortLomuto partition

Counting Sort

syntax
Count occurrences of each value.
Build output array from the counts.
Only works when the range of values is bounded.
example
// JavaScript
function countingSort(arr, maxVal) {
  const count = new Array(maxVal + 1).fill(0);
  for (const val of arr) count[val]++;
  const result = [];
  for (let i = 0; i <= maxVal; i++) {
    for (let j = 0; j < count[i]; j++) {
      result.push(i);
    }
  }
  return result;
}

# Python
def counting_sort(arr, max_val):
    count = [0] * (max_val + 1)
    for val in arr:
        count[val] += 1
    result = []
    for i in range(max_val + 1):
        result.extend([i] * count[i])
    return result
output
counting_sort([4,2,2,8,3,3,1], 8) → [1,2,2,3,3,4,8]

Note Time: O(n + k) where k = value range. Space: O(k). Beats comparison-based O(n log n) when k is small. Not suitable for large ranges or floating-point numbers. Radix sort extends this to handle larger ranges digit by digit.

counting sortnon-comparison sortinteger sortbounded range sort

When to Use Which Sort

syntax
Small n (< 20): insertion sort
General purpose: merge sort (stable) or quicksort (fast avg)
Bounded integers: counting/radix sort
Nearly sorted: insertion sort
Linked lists: merge sort
Stability needed: merge sort or TimSort
example
// JavaScript — just use built-in for interviews
const nums = [5, 3, 8, 1];
nums.sort((a, b) => a - b);  // ALWAYS pass comparator for numbers!
// Without comparator, JS sorts lexicographically: [1, 3, 5, 8]
// But [10, 9, 80].sort() → [10, 80, 9] — WRONG!

# Python
nums = [5, 3, 8, 1]
nums.sort()               # in-place, returns None
sorted_nums = sorted(nums) # returns new list
# Custom: sorted(items, key=lambda x: x[1])
output
Built-in sorts: JS uses TimSort, Python uses TimSort — both O(n log n)

Note In interviews, use the built-in sort unless asked to implement one. JS trap: .sort() without a comparator converts elements to strings — always pass (a,b) => a-b for numbers. Know the trade-offs between sorts for the 'which sort would you use' question.

which sort to usesorting comparisonbuilt-in sortsort comparatorTimSort

Sort Stability

syntax
A stable sort preserves the relative order of elements with equal keys.
Stable: merge sort, insertion sort, bubble sort, TimSort.
Unstable: quicksort, selection sort, heap sort.
example
// JavaScript — Stability matters for multi-key sorting
const students = [
  { name: 'Alice', grade: 'B' },
  { name: 'Bob',   grade: 'A' },
  { name: 'Carol', grade: 'B' },
  { name: 'Dave',  grade: 'A' },
];
// Sort by grade — stable sort keeps Alice before Carol (both B)
students.sort((a, b) => a.grade.localeCompare(b.grade));
// Result: Bob, Dave, Alice, Carol (A's first, original order preserved)

# Python
students = [('Alice','B'), ('Bob','A'), ('Carol','B'), ('Dave','A')]
students.sort(key=lambda x: x[1])
# [('Bob','A'), ('Dave','A'), ('Alice','B'), ('Carol','B')]
output
Stable: equal elements keep original relative order.
Unstable: equal elements may be reordered.

Note Stability matters when sorting by multiple criteria (e.g., sort by grade, then by name within same grade). Python's sort is guaranteed stable. JS sort stability was implementation-dependent before ES2019 but is now required to be stable in the spec.

sort stabilitystable sortunstable sortmulti-key sortrelative order