Stable sort

4 snippets in Interview Prep

DSAInterview Prep

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.

Insertion Sort

DSA · Sorting

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.

Merge Sort

DSA · Sorting

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.

Sort Stability

DSA · Sorting

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.