SyntaxShelf

Stable sort

4 snippets in Interview Prep

DSAInterview Prep

Bubble Sort

DSA · Sorting
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.

Frequently asked questions

How does Interview Prep handle stable sort?
Interview Prep covers this with 4 copy-ready snippets on this page. The "Bubble Sort" snippet in Interview Prep uses `Repeatedly swap adjacent elements if out of order.`.
Which code does the Interview Prep example use?
The "Bubble Sort" snippet uses `Repeatedly swap adjacent elements if out of order.`, from the Sorting section of the Interview Prep cheat sheet.
What other Interview Prep snippets are shown for "stable sort"?
Besides "Bubble Sort", this page also shows "Insertion Sort", "Merge Sort", "Sort Stability".
Is there anything to watch out for?
Yes. For "Bubble Sort": 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.

Browse all tasks by intent