Introduction

Sorting and searching are the two most fundamental operations in computer science. Every database query, every search engine result, every autocomplete suggestion relies on efficient sorting and searching algorithms under the hood.

In coding interviews, sorting problems test your understanding of divide and conquer, comparison-based logic, and stability. Binary search problems test your ability to eliminate half the search space systematically — one of the most powerful algorithmic techniques you'll ever learn.

This post covers Part 1: Sorting Algorithms and Part 2: Binary Search from our DSA series. By the end, you'll understand when to use each algorithm, why they work, and how to implement them from scratch.

What You'll Learn

✅ Understand comparison-based vs non-comparison sorting
✅ Implement Bubble Sort, Selection Sort, Insertion Sort, Merge Sort, Quick Sort
✅ Analyze time and space complexity for each sorting algorithm
✅ Master standard binary search and its variations
✅ Apply binary search to rotated arrays, search spaces, and answer validation
✅ Solve 8 classic interview problems step-by-step

Prerequisites

Understanding of Big O Notation & Complexity Analysis
Familiarity with Problem-Solving Patterns
Completed Arrays & Strings
Basic programming knowledge in TypeScript or Python

Part 1: Sorting Algorithms

1. Why Sorting Matters

Sorting is more than just arranging elements in order. Many algorithms require sorted input as a prerequisite:

Depends on Sorting	Algorithm
Binary search	Requires sorted array
Two pointers	Often needs sorted input
Merge intervals	Sort by start time first
Closest pair	Sort then scan neighbors
Kruskal's MST	Sort edges by weight
Median finding	Sorted order gives O(1) median

"If your brute force is O(n²) and the input isn't sorted, your first instinct should be: can I sort it first?"

Sorting an array costs O(n log n), which is "almost free" compared to O(n²) brute force approaches. Many O(n²) problems become O(n log n) just by sorting first.

2. Sorting Algorithm Classification

Key Properties to Compare:

Property	Definition
Stable	Equal elements maintain their original relative order
In-place	Uses O(1) extra memory (sorts within the array itself)
Adaptive	Runs faster on partially sorted input
Online	Can sort elements as they arrive (doesn't need all data upfront)

3. Elementary Sorting Algorithms — O(n²)

These are simple but slow. You should know them for interviews, but rarely use them in production.

3.1 Bubble Sort

Idea: Repeatedly step through the array, swap adjacent elements if they're in the wrong order. The largest unsorted element "bubbles up" to its correct position each pass.

// TypeScript - Bubble Sort
function bubbleSort(arr: number[]): number[] {
  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;
      }
    }
    // Optimization: if no swaps, array is sorted
    if (!swapped) break;
  }
  return arr;
}
 
console.log(bubbleSort([5, 3, 8, 1, 2])); // [1, 2, 3, 5, 8]

# Python - Bubble Sort
def bubble_sort(arr: list[int]) -> list[int]:
    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
        # Optimization: if no swaps, array is sorted
        if not swapped:
            break
    return arr
 
print(bubble_sort([5, 3, 8, 1, 2]))  # [1, 2, 3, 5, 8]

Property	Value
Time (Best)	O(n) — already sorted, with optimization
Time (Average/Worst)	O(n²)
Space	O(1) in-place
Stable	✅ Yes
Adaptive	✅ Yes (with swapped flag)

When to use: Almost never in practice. Good for teaching and understanding sorting basics.

3.2 Selection Sort

Idea: Find the minimum element in the unsorted portion and swap it to the front. Repeat for each position.

// TypeScript - Selection Sort
function selectionSort(arr: number[]): number[] {
  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;
      }
    }
    if (minIdx !== i) {
      [arr[i], arr[minIdx]] = [arr[minIdx], arr[i]];
    }
  }
  return arr;
}

# Python - Selection Sort
def selection_sort(arr: list[int]) -> list[int]:
    n = len(arr)
    for i in range(n - 1):
        min_idx = i
        for j in range(i + 1, n):
            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

Property	Value
Time (All cases)	O(n²) — always scans full unsorted portion
Space	O(1) in-place
Stable	❌ No (swaps can change relative order)
Adaptive	❌ No

When to use: When memory writes are expensive (minimizes swaps — at most n swaps).

3.3 Insertion Sort

Idea: Build the sorted array one element at a time. Take each element and insert it into its correct position in the already-sorted prefix.

Think of it like sorting playing cards — you pick up one card at a time and slide it into the right spot in your hand.

// TypeScript - Insertion Sort
function insertionSort(arr: number[]): number[] {
  const n = arr.length;
  for (let i = 1; i < n; i++) {
    const key = arr[i];
    let j = i - 1;
    // Shift elements greater than key to the right
    while (j >= 0 && arr[j] > key) {
      arr[j + 1] = arr[j];
      j--;
    }
    arr[j + 1] = key;
  }
  return arr;
}

# Python - Insertion Sort
def insertion_sort(arr: list[int]) -> list[int]:
    n = len(arr)
    for i in range(1, n):
        key = arr[i]
        j = i - 1
        # Shift elements greater than key to the right
        while j >= 0 and arr[j] > key:
            arr[j + 1] = arr[j]
            j -= 1
        arr[j + 1] = key
    return arr

Property	Value
Time (Best)	O(n) — already sorted
Time (Average/Worst)	O(n²)
Space	O(1) in-place
Stable	✅ Yes
Adaptive	✅ Yes
Online	✅ Yes

When to use: Small arrays (< 20 elements), nearly-sorted data, or as the base case for hybrid sorts (TimSort uses insertion sort for small partitions).

4. Efficient Sorting Algorithms — O(n log n)

These are the workhorses of real-world sorting. Understand these deeply.

4.1 Merge Sort

Idea: Divide the array in half, recursively sort each half, then merge the two sorted halves. This is the classic divide and conquer algorithm.

// TypeScript - 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]);
      i++;
    } else {
      result.push(right[j]);
      j++;
    }
  }
 
  // Append remaining elements
  while (i < left.length) result.push(left[i++]);
  while (j < right.length) result.push(right[j++]);
 
  return result;
}
 
console.log(mergeSort([38, 27, 43, 3, 9, 82, 10]));
// [3, 9, 10, 27, 38, 43, 82]

# Python - Merge Sort
def merge_sort(arr: list[int]) -> list[int]:
    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(left: list[int], right: list[int]) -> list[int]:
    result = []
    i = j = 0
 
    while i < len(left) and j < len(right):
        if left[i] <= right[j]:
            result.append(left[i])
            i += 1
        else:
            result.append(right[j])
            j += 1
 
    # Append remaining elements
    result.extend(left[i:])
    result.extend(right[j:])
    return result
 
print(merge_sort([38, 27, 43, 3, 9, 82, 10]))
# [3, 9, 10, 27, 38, 43, 82]

How the merge step works:

Left:  [3, 27, 38, 43]    Right: [9, 10, 82]
        ↑ i=0                      ↑ j=0
 
Step 1: 3 < 9   → take 3    Result: [3]
Step 2: 27 > 9  → take 9    Result: [3, 9]
Step 3: 27 > 10 → take 10   Result: [3, 9, 10]
Step 4: 27 < 82 → take 27   Result: [3, 9, 10, 27]
Step 5: 38 < 82 → take 38   Result: [3, 9, 10, 27, 38]
Step 6: 43 < 82 → take 43   Result: [3, 9, 10, 27, 38, 43]
Step 7: append 82            Result: [3, 9, 10, 27, 38, 43, 82]

Property	Value
Time (All cases)	O(n log n) — always divides and merges
Space	O(n) — needs temporary arrays for merging
Stable	✅ Yes (equal elements maintain order)
Adaptive	❌ No (always O(n log n))

When to use: When stability is required, linked list sorting, external sorting (data too large for memory), or when guaranteed O(n log n) is needed.

Why O(n log n)?

log n levels of recursion (halving the array each time)
O(n) work at each level (merging all elements)
Total: O(n) × O(log n) = O(n log n)

4.2 Quick Sort

Idea: Choose a pivot element, partition the array so all elements less than pivot go left and all greater go right, then recursively sort left and right partitions.

// TypeScript - Quick Sort (Lomuto partition)
function quickSort(arr: number[], low: number = 0, high: number = arr.length - 1): number[] {
  if (low < high) {
    const pivotIdx = partition(arr, low, high);
    quickSort(arr, low, pivotIdx - 1);
    quickSort(arr, pivotIdx + 1, high);
  }
  return arr;
}
 
function partition(arr: number[], low: number, high: number): number {
  const pivot = arr[high]; // Choose last element as pivot
  let i = low - 1;        // Index of smaller element boundary
 
  for (let j = low; j < high; j++) {
    if (arr[j] <= pivot) {
      i++;
      [arr[i], arr[j]] = [arr[j], arr[i]];
    }
  }
 
  // Place pivot in its correct position
  [arr[i + 1], arr[high]] = [arr[high], arr[i + 1]];
  return i + 1;
}
 
console.log(quickSort([8, 3, 1, 7, 0, 10, 2]));
// [0, 1, 2, 3, 7, 8, 10]

# Python - Quick Sort (Lomuto partition)
def quick_sort(arr: list[int], low: int = 0, high: int = None) -> list[int]:
    if high is None:
        high = len(arr) - 1
 
    if low < high:
        pivot_idx = partition(arr, low, high)
        quick_sort(arr, low, pivot_idx - 1)
        quick_sort(arr, pivot_idx + 1, high)
 
    return arr
 
def partition(arr: list[int], low: int, high: int) -> int:
    pivot = arr[high]  # Choose last element as pivot
    i = low - 1        # Index of smaller element boundary
 
    for j in range(low, high):
        if arr[j] <= pivot:
            i += 1
            arr[i], arr[j] = arr[j], arr[i]
 
    # Place pivot in its correct position
    arr[i + 1], arr[high] = arr[high], arr[i + 1]
    return i + 1
 
print(quick_sort([8, 3, 1, 7, 0, 10, 2]))
# [0, 1, 2, 3, 7, 8, 10]

Partition trace for [8, 3, 1, 7, 0, 10, 2], pivot = 2:

Initial: [8, 3, 1, 7, 0, 10, 2]  pivot=2, i=-1
 
j=0: 8 > 2  → skip
j=1: 3 > 2  → skip
j=2: 1 ≤ 2  → i=0, swap(0,2) → [1, 3, 8, 7, 0, 10, 2]
j=3: 7 > 2  → skip
j=4: 0 ≤ 2  → i=1, swap(1,4) → [1, 0, 8, 7, 3, 10, 2]
j=5: 10 > 2 → skip
 
Place pivot: swap(i+1=2, high=6) → [1, 0, 2, 7, 3, 10, 8]
                                          ↑ pivot at index 2

Property	Value
Time (Best/Average)	O(n log n)
Time (Worst)	O(n²) — already sorted + bad pivot
Space	O(log n) — recursion stack
Stable	❌ No
Adaptive	❌ No

Pivot selection strategies:

Strategy	Pros	Cons
Last element	Simple	O(n²) on sorted input
Random element	Avoids worst case	Extra random call
Median-of-three	Good practical performance	Slightly more complex

When to use: Default choice for in-memory sorting. Most standard library sorts use Quick Sort variants (or hybrid sorts like IntroSort).

4.3 Merge Sort vs Quick Sort

Aspect	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
Cache performance	Poor (not in-place)	Excellent (in-place)
Best for	Linked lists, external sort	Arrays, in-memory sort
Used by	Python (Timsort), Java (objects)	C++ (IntroSort), Java (primitives)

Interview tip: If asked "which sorting algorithm is best?", the answer is always "it depends." Mention the trade-offs above.

5. Sorting Algorithm Comparison Summary

Algorithm	Best	Average	Worst	Space	Stable	In-Place
Bubble Sort	O(n)	O(n²)	O(n²)	O(1)	✅	✅
Selection Sort	O(n²)	O(n²)	O(n²)	O(1)	❌	✅
Insertion Sort	O(n)	O(n²)	O(n²)	O(1)	✅	✅
Merge Sort	O(n log n)	O(n log n)	O(n log n)	O(n)	✅	❌
Quick Sort	O(n log n)	O(n log n)	O(n²)	O(log n)	❌	✅
Heap Sort	O(n log n)	O(n log n)	O(n log n)	O(1)	❌	✅

Key takeaways:

O(n log n) is the theoretical lower bound for comparison-based sorting
Merge Sort = guaranteed O(n log n), stable, but uses O(n) space
Quick Sort = fastest in practice, in-place, but worst case O(n²)
Insertion Sort = best for small or nearly-sorted arrays
Real-world sorts are hybrids: TimSort (Python, Java) combines Merge Sort + Insertion Sort

Built-in Sorts: What Languages Use

// TypeScript/JavaScript - TimSort (stable, O(n log n))
const arr = [3, 1, 4, 1, 5, 9];
arr.sort((a, b) => a - b);  // Always provide comparator for numbers!
// Without comparator, JS sorts as strings: [1, 1, 3, 4, 5, 9]

# Python - TimSort (stable, O(n log n))
arr = [3, 1, 4, 1, 5, 9]
arr.sort()              # In-place sort
sorted_arr = sorted(arr)  # Returns new sorted list
 
# Custom sort
intervals = [(2, 3), (1, 5), (1, 2)]
intervals.sort(key=lambda x: (x[0], x[1]))
# [(1, 2), (1, 5), (2, 3)]

Interview tip: In actual interviews, use built-in sorts unless asked to implement from scratch. Know how they work, but don't reinvent the wheel.

Part 2: Binary Search

6. Binary Search Fundamentals

Binary search is one of the most powerful techniques in computer science. The core idea is simple: if your search space is sorted (or has a monotonic property), you can eliminate half of it with each comparison.

Linear Search:  [1, 3, 5, 7, 9, 11, 13, 15]  → Check each one: O(n)
Binary Search:  [1, 3, 5, 7, 9, 11, 13, 15]  → Check middle, eliminate half: O(log n)

6.1 How Fast is O(log n)?

Array Size (n)	Linear Search O(n)	Binary Search O(log n)
100	100 steps	7 steps
10,000	10,000 steps	14 steps
1,000,000	1,000,000 steps	20 steps
1,000,000,000	1 billion steps	30 steps

Binary search on 1 billion elements takes at most 30 steps. That's the power of logarithmic time.

6.2 Standard Binary Search

// TypeScript - Standard Binary Search
function binarySearch(arr: number[], target: number): number {
  let left = 0;
  let right = arr.length - 1;
 
  while (left <= right) {
    const mid = Math.floor(left + (right - left) / 2); // Avoid overflow
 
    if (arr[mid] === target) {
      return mid;      // Found it
    } else if (arr[mid] < target) {
      left = mid + 1;  // Target is in right half
    } else {
      right = mid - 1; // Target is in left half
    }
  }
 
  return -1; // Not found
}
 
console.log(binarySearch([1, 3, 5, 7, 9, 11], 7));  // 3
console.log(binarySearch([1, 3, 5, 7, 9, 11], 6));  // -1

# Python - Standard Binary Search
def binary_search(arr: list[int], target: int) -> int:
    left, right = 0, len(arr) - 1
 
    while left <= right:
        mid = left + (right - left) // 2  # Avoid overflow
 
        if arr[mid] == target:
            return mid       # Found it
        elif arr[mid] < target:
            left = mid + 1   # Target is in right half
        else:
            right = mid - 1  # Target is in left half
 
    return -1  # Not found
 
print(binary_search([1, 3, 5, 7, 9, 11], 7))   # 3
print(binary_search([1, 3, 5, 7, 9, 11], 6))   # -1

Trace example — searching for 7 in [1, 3, 5, 7, 9, 11]:

Step 1: left=0, right=5, mid=2 → arr[2]=5 < 7  → left=3
Step 2: left=3, right=5, mid=4 → arr[4]=9 > 7  → right=3
Step 3: left=3, right=3, mid=3 → arr[3]=7 = 7  → return 3 ✓

6.3 Common Binary Search Bugs

Binary search is notoriously easy to get wrong. Here are the most common mistakes:

Bug	Wrong Code	Correct Code
Integer overflow	`mid = (left + right) / 2`	`mid = left + (right - left) / 2`
Infinite loop	`left = mid` or `right = mid`	`left = mid + 1` or `right = mid - 1`
Off-by-one	`while (left < right)` vs `while (left <= right)`	Depends on the variant (see below)
Wrong boundary	Searching past array bounds	Always check `left <= right`

7. Binary Search Patterns

The standard binary search is just the beginning. The real power of binary search comes from its variations. Let's master the three core patterns.

7.1 Pattern 1: Find Exact Value

This is the standard binary search we already saw. Use while (left <= right) with left = mid + 1 and right = mid - 1.

Template: Return the index where arr[mid] === target, or -1 if not found.

7.2 Pattern 2: Find First/Last Position (Boundary Search)

This is the most important binary search pattern for interviews. Instead of finding any occurrence, find the first or last position that satisfies a condition.

Find First Position ≥ Target (Lower Bound):

// TypeScript - Find first position where arr[mid] >= target
function lowerBound(arr: number[], target: number): number {
  let left = 0;
  let right = arr.length; // Note: right = length (not length-1)
 
  while (left < right) {  // Note: strict < (not <=)
    const mid = Math.floor(left + (right - left) / 2);
    if (arr[mid] < target) {
      left = mid + 1;
    } else {
      right = mid;  // Note: right = mid (not mid-1)
    }
  }
 
  return left; // First position where arr[left] >= target
}
 
// Example: [1, 3, 3, 5, 7]
// lowerBound(arr, 3) → 1 (first index where value >= 3)
// lowerBound(arr, 4) → 3 (first index where value >= 4, which is 5)
// lowerBound(arr, 8) → 5 (past the end, target > all elements)

# Python - Find first position where arr[mid] >= target
def lower_bound(arr: list[int], target: int) -> int:
    left, right = 0, len(arr)  # right = len(arr), not len(arr)-1
 
    while left < right:  # strict < (not <=)
        mid = left + (right - left) // 2
        if arr[mid] < target:
            left = mid + 1
        else:
            right = mid  # right = mid (not mid-1)
 
    return left  # First position where arr[left] >= target
 
# Python also has built-in:
import bisect
bisect.bisect_left([1, 3, 3, 5, 7], 3)   # 1
bisect.bisect_right([1, 3, 3, 5, 7], 3)  # 3

Find Last Position ≤ Target (Upper Bound):

// TypeScript - Find last position where arr[mid] <= target
function upperBound(arr: number[], target: number): number {
  let left = 0;
  let right = arr.length;
 
  while (left < right) {
    const mid = Math.floor(left + (right - left) / 2);
    if (arr[mid] <= target) {
      left = mid + 1;
    } else {
      right = mid;
    }
  }
 
  return left - 1; // Last position where arr[left-1] <= target
}
 
// Example: [1, 3, 3, 5, 7]
// upperBound(arr, 3) → 2 (last index where value <= 3)
// upperBound(arr, 4) → 2 (last index where value <= 4, which is 3)

When to use each:

Need	Function	Returns
First occurrence of target	`lowerBound(arr, target)` then check `arr[result] === target`
Last occurrence of target	`upperBound(arr, target)` then check `arr[result] === target`
Count of target	`upperBound(target) - lowerBound(target) + 1`
Insert position	`lowerBound(arr, target)`

7.3 Pattern 3: Binary Search on Answer (Search Space Reduction)

This is the most advanced and powerful pattern. Instead of searching in an array, you binary search on the answer space.

Key insight: If you can define a function canAchieve(x) that returns true for all values ≥ some threshold and false below it (monotonic), you can binary search for that threshold.

Answer space:  [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
canAchieve:    [F, F, F, F, T, T, T, T, T, T]
                              ↑ Find this boundary

// TypeScript - Binary Search on Answer template
function binarySearchOnAnswer(low: number, high: number): number {
  while (low < high) {
    const mid = Math.floor(low + (high - low) / 2);
    if (canAchieve(mid)) {
      high = mid;     // mid might be the answer, search left
    } else {
      low = mid + 1;  // mid is too small, search right
    }
  }
  return low;
}

# Python - Binary Search on Answer template
def binary_search_on_answer(low: int, high: int) -> int:
    while low < high:
        mid = low + (high - low) // 2
        if can_achieve(mid):
            high = mid      # mid might be the answer, search left
        else:
            low = mid + 1   # mid is too small, search right
    return low

We'll see this pattern in action with interview problems below.

8. Interview Problems: Sorting

Problem 1: Sort Colors (Dutch National Flag)

LeetCode 75: Given an array with elements 0, 1, 2, sort it in-place in one pass.

Key insight: Three-pointer technique — maintain boundaries for 0s, 1s, and 2s.

// TypeScript - Sort Colors (One-pass, O(n) time, O(1) space)
function sortColors(nums: number[]): void {
  let low = 0;      // Boundary: everything before low is 0
  let mid = 0;      // Current element
  let high = nums.length - 1; // Boundary: everything after high is 2
 
  while (mid <= high) {
    if (nums[mid] === 0) {
      [nums[low], nums[mid]] = [nums[mid], nums[low]];
      low++;
      mid++;
    } else if (nums[mid] === 1) {
      mid++;
    } else {
      // nums[mid] === 2
      [nums[mid], nums[high]] = [nums[high], nums[mid]];
      high--;
      // Don't increment mid — swapped element needs checking
    }
  }
}
 
const colors = [2, 0, 2, 1, 1, 0];
sortColors(colors);
console.log(colors); // [0, 0, 1, 1, 2, 2]

# Python - Sort Colors (One-pass, O(n) time, O(1) space)
def sort_colors(nums: list[int]) -> None:
    low, mid, high = 0, 0, len(nums) - 1
 
    while mid <= high:
        if nums[mid] == 0:
            nums[low], nums[mid] = nums[mid], nums[low]
            low += 1
            mid += 1
        elif nums[mid] == 1:
            mid += 1
        else:
            nums[mid], nums[high] = nums[high], nums[mid]
            high -= 1
            # Don't increment mid — swapped element needs checking
 
colors = [2, 0, 2, 1, 1, 0]
sort_colors(colors)
print(colors)  # [0, 0, 1, 1, 2, 2]

Trace:

[2, 0, 2, 1, 1, 0]  low=0, mid=0, high=5
 ↑mid         ↑high
nums[0]=2 → swap(0,5) → [0, 0, 2, 1, 1, 2]  high=4
 
[0, 0, 2, 1, 1, 2]  low=0, mid=0, high=4
 ↑mid      ↑high
nums[0]=0 → swap(0,0) → [0, 0, 2, 1, 1, 2]  low=1, mid=1
 
nums[1]=0 → swap(1,1) → [0, 0, 2, 1, 1, 2]  low=2, mid=2
 
nums[2]=2 → swap(2,4) → [0, 0, 1, 1, 2, 2]  high=3
 
nums[2]=1 → mid=3
 
nums[3]=1 → mid=4  → mid > high → DONE ✓
Result: [0, 0, 1, 1, 2, 2]

Problem 2: Merge Intervals

LeetCode 56: Given a collection of intervals, merge all overlapping intervals.

Key insight: Sort by start time, then merge adjacent intervals that overlap.

// TypeScript - Merge Intervals
function mergeIntervals(intervals: number[][]): number[][] {
  if (intervals.length <= 1) return intervals;
 
  // Sort by start time
  intervals.sort((a, b) => a[0] - b[0]);
 
  const merged: number[][] = [intervals[0]];
 
  for (let i = 1; i < intervals.length; i++) {
    const current = intervals[i];
    const last = merged[merged.length - 1];
 
    if (current[0] <= last[1]) {
      // Overlapping — extend the end
      last[1] = Math.max(last[1], current[1]);
    } else {
      // No overlap — add new interval
      merged.push(current);
    }
  }
 
  return merged;
}
 
console.log(mergeIntervals([[1,3],[2,6],[8,10],[15,18]]));
// [[1,6],[8,10],[15,18]]

# Python - Merge Intervals
def merge_intervals(intervals: list[list[int]]) -> list[list[int]]:
    if len(intervals) <= 1:
        return intervals
 
    # Sort by start time
    intervals.sort(key=lambda x: x[0])
 
    merged = [intervals[0]]
 
    for current in intervals[1:]:
        last = merged[-1]
 
        if current[0] <= last[1]:
            # Overlapping — extend the end
            last[1] = max(last[1], current[1])
        else:
            # No overlap — add new interval
            merged.append(current)
 
    return merged
 
print(merge_intervals([[1,3],[2,6],[8,10],[15,18]]))
# [[1,6],[8,10],[15,18]]

Time: O(n log n) for sorting + O(n) for merging = O(n log n)
Space: O(n) for the result

Problem 3: Kth Largest Element

LeetCode 215: Find the kth largest element in an unsorted array.

Key insight: Use Quick Select — a variant of Quick Sort that only recurses into one partition.

// TypeScript - Kth Largest Element (Quick Select)
function findKthLargest(nums: number[], k: number): number {
  // kth largest = (n - k)th smallest (0-indexed)
  const targetIdx = nums.length - k;
  return quickSelect(nums, 0, nums.length - 1, targetIdx);
}
 
function quickSelect(arr: number[], low: number, high: number, target: number): number {
  if (low === high) return arr[low];
 
  // Random pivot to avoid worst case
  const randomIdx = low + Math.floor(Math.random() * (high - low + 1));
  [arr[randomIdx], arr[high]] = [arr[high], arr[randomIdx]];
 
  const pivotIdx = partition(arr, low, high);
 
  if (pivotIdx === target) {
    return arr[pivotIdx];
  } else if (pivotIdx < target) {
    return quickSelect(arr, pivotIdx + 1, high, target);
  } else {
    return quickSelect(arr, low, pivotIdx - 1, target);
  }
}
 
// Reuses the partition function from Quick Sort (Section 4.2)
 
console.log(findKthLargest([3, 2, 1, 5, 6, 4], 2)); // 5
console.log(findKthLargest([3, 2, 3, 1, 2, 4, 5, 5, 6], 4)); // 4

# Python - Kth Largest Element (Quick Select)
import random
 
def find_kth_largest(nums: list[int], k: int) -> int:
    target_idx = len(nums) - k  # kth largest = (n-k)th smallest
    return quick_select(nums, 0, len(nums) - 1, target_idx)
 
def quick_select(arr: list[int], low: int, high: int, target: int) -> int:
    if low == high:
        return arr[low]
 
    # Random pivot to avoid worst case
    random_idx = random.randint(low, high)
    arr[random_idx], arr[high] = arr[high], arr[random_idx]
 
    pivot_idx = qs_partition(arr, low, high)
 
    if pivot_idx == target:
        return arr[pivot_idx]
    elif pivot_idx < target:
        return quick_select(arr, pivot_idx + 1, high, target)
    else:
        return quick_select(arr, low, pivot_idx - 1, target)
 
def qs_partition(arr: list[int], low: int, high: int) -> int:
    pivot = arr[high]
    i = low - 1
    for j in range(low, high):
        if arr[j] <= pivot:
            i += 1
            arr[i], arr[j] = arr[j], arr[i]
    arr[i + 1], arr[high] = arr[high], arr[i + 1]
    return i + 1
 
print(find_kth_largest([3, 2, 1, 5, 6, 4], 2))  # 5

Time: O(n) average, O(n²) worst case
Space: O(1) — in-place partitioning

Why O(n)? On average, each recursive call works on half the elements: n + n/2 + n/4 + ... = 2n = O(n).

9. Interview Problems: Binary Search

Problem 4: Search in Rotated Sorted Array

LeetCode 33: Search for a target in an array that was sorted then rotated at some pivot.

Key insight: At least one half of the array is always sorted. Determine which half, and check if the target falls in that half.

Original sorted: [0, 1, 2, 4, 5, 6, 7]
Rotated at idx 4: [4, 5, 6, 7, 0, 1, 2]
                   ↑ sorted ↑  ↑ sorted ↑

// TypeScript - Search in Rotated Sorted Array
function searchRotated(nums: number[], target: number): number {
  let left = 0;
  let right = nums.length - 1;
 
  while (left <= right) {
    const mid = Math.floor(left + (right - left) / 2);
 
    if (nums[mid] === target) return mid;
 
    // Determine which half is sorted
    if (nums[left] <= nums[mid]) {
      // Left half is sorted
      if (nums[left] <= target && target < nums[mid]) {
        right = mid - 1; // Target in sorted left half
      } else {
        left = mid + 1;  // Target in right half
      }
    } else {
      // Right half is sorted
      if (nums[mid] < target && target <= nums[right]) {
        left = mid + 1;  // Target in sorted right half
      } else {
        right = mid - 1; // Target in left half
      }
    }
  }
 
  return -1;
}
 
console.log(searchRotated([4, 5, 6, 7, 0, 1, 2], 0)); // 4
console.log(searchRotated([4, 5, 6, 7, 0, 1, 2], 3)); // -1

# Python - Search in Rotated Sorted Array
def search_rotated(nums: list[int], target: int) -> int:
    left, right = 0, len(nums) - 1
 
    while left <= right:
        mid = left + (right - left) // 2
 
        if nums[mid] == target:
            return mid
 
        # Determine which half is sorted
        if nums[left] <= nums[mid]:
            # Left half is sorted
            if nums[left] <= target < nums[mid]:
                right = mid - 1  # Target in sorted left half
            else:
                left = mid + 1   # Target in right half
        else:
            # Right half is sorted
            if nums[mid] < target <= nums[right]:
                left = mid + 1   # Target in sorted right half
            else:
                right = mid - 1  # Target in left half
 
    return -1
 
print(search_rotated([4, 5, 6, 7, 0, 1, 2], 0))  # 4

Trace for target=0 in [4, 5, 6, 7, 0, 1, 2]:

Step 1: left=0, right=6, mid=3 → nums[3]=7 ≠ 0
        nums[0]=4 <= nums[3]=7 → left half sorted [4,5,6,7]
        0 not in [4, 7) → left = 4
 
Step 2: left=4, right=6, mid=5 → nums[5]=1 ≠ 0
        nums[4]=0 <= nums[5]=1 → left half sorted [0,1]
        0 in [0, 1) → right = 4
 
Step 3: left=4, right=4, mid=4 → nums[4]=0 = 0 → return 4 ✓

Problem 5: Find First and Last Position

LeetCode 34: Find the starting and ending position of a given target value in a sorted array.

Key insight: Use two binary searches — one to find the first occurrence, one to find the last.

// TypeScript - Find First and Last Position
function searchRange(nums: number[], target: number): number[] {
  return [findFirst(nums, target), findLast(nums, target)];
}
 
function findFirst(nums: number[], target: number): number {
  let left = 0, right = nums.length - 1;
  let result = -1;
 
  while (left <= right) {
    const mid = Math.floor(left + (right - left) / 2);
    if (nums[mid] === target) {
      result = mid;
      right = mid - 1;  // Keep searching left for earlier occurrence
    } else if (nums[mid] < target) {
      left = mid + 1;
    } else {
      right = mid - 1;
    }
  }
 
  return result;
}
 
function findLast(nums: number[], target: number): number {
  let left = 0, right = nums.length - 1;
  let result = -1;
 
  while (left <= right) {
    const mid = Math.floor(left + (right - left) / 2);
    if (nums[mid] === target) {
      result = mid;
      left = mid + 1;   // Keep searching right for later occurrence
    } else if (nums[mid] < target) {
      left = mid + 1;
    } else {
      right = mid - 1;
    }
  }
 
  return result;
}
 
console.log(searchRange([5,7,7,8,8,10], 8)); // [3, 4]
console.log(searchRange([5,7,7,8,8,10], 6)); // [-1, -1]

# Python - Find First and Last Position
def search_range(nums: list[int], target: int) -> list[int]:
    return [find_first(nums, target), find_last(nums, target)]
 
def find_first(nums: list[int], target: int) -> int:
    left, right = 0, len(nums) - 1
    result = -1
 
    while left <= right:
        mid = left + (right - left) // 2
        if nums[mid] == target:
            result = mid
            right = mid - 1  # Keep searching left
        elif nums[mid] < target:
            left = mid + 1
        else:
            right = mid - 1
 
    return result
 
def find_last(nums: list[int], target: int) -> int:
    left, right = 0, len(nums) - 1
    result = -1
 
    while left <= right:
        mid = left + (right - left) // 2
        if nums[mid] == target:
            result = mid
            left = mid + 1  # Keep searching right
        elif nums[mid] < target:
            left = mid + 1
        else:
            right = mid - 1
 
    return result
 
print(search_range([5,7,7,8,8,10], 8))  # [3, 4]

Time: O(log n) — two binary searches
Space: O(1)

Problem 6: Find Peak Element

LeetCode 162: Find a peak element (element greater than its neighbors) in O(log n).

Key insight: If arr[mid] < arr[mid+1], a peak must exist on the right. If arr[mid] > arr[mid+1], a peak must exist on the left (or at mid).

// TypeScript - Find Peak Element
function findPeakElement(nums: number[]): number {
  let left = 0;
  let right = nums.length - 1;
 
  while (left < right) {
    const mid = Math.floor(left + (right - left) / 2);
 
    if (nums[mid] < nums[mid + 1]) {
      left = mid + 1;  // Peak is on the right
    } else {
      right = mid;     // Peak is at mid or on the left
    }
  }
 
  return left; // left === right, pointing to peak
}
 
console.log(findPeakElement([1, 2, 3, 1]));    // 2 (value 3)
console.log(findPeakElement([1, 2, 1, 3, 5, 6, 4])); // 5 (value 6)

# Python - Find Peak Element
def find_peak_element(nums: list[int]) -> int:
    left, right = 0, len(nums) - 1
 
    while left < right:
        mid = left + (right - left) // 2
 
        if nums[mid] < nums[mid + 1]:
            left = mid + 1   # Peak is on the right
        else:
            right = mid      # Peak is at mid or on the left
 
    return left  # left == right, pointing to peak
 
print(find_peak_element([1, 2, 3, 1]))    # 2
print(find_peak_element([1, 2, 1, 3, 5, 6, 4]))  # 5

Time: O(log n)
Space: O(1)

Why this works: The array boundaries are -∞, so if we're going "uphill" (increasing), we must eventually hit a peak before falling to -∞ at the edge.

Problem 7: Minimum in Rotated Sorted Array

LeetCode 153: Find the minimum element in a rotated sorted array (no duplicates).

Key insight: Compare mid with right. If arr[mid] > arr[right], the minimum is in the right half. Otherwise, it's in the left half (including mid).

// TypeScript - Find Minimum in Rotated Sorted Array
function findMin(nums: number[]): number {
  let left = 0;
  let right = nums.length - 1;
 
  while (left < right) {
    const mid = Math.floor(left + (right - left) / 2);
 
    if (nums[mid] > nums[right]) {
      left = mid + 1;  // Minimum is in right half
    } else {
      right = mid;     // Minimum is at mid or in left half
    }
  }
 
  return nums[left];
}
 
console.log(findMin([3, 4, 5, 1, 2]));    // 1
console.log(findMin([4, 5, 6, 7, 0, 1, 2])); // 0
console.log(findMin([11, 13, 15, 17]));    // 11 (not rotated)

# Python - Find Minimum in Rotated Sorted Array
def find_min(nums: list[int]) -> int:
    left, right = 0, len(nums) - 1
 
    while left < right:
        mid = left + (right - left) // 2
 
        if nums[mid] > nums[right]:
            left = mid + 1   # Minimum is in right half
        else:
            right = mid      # Minimum is at mid or left half
 
    return nums[left]
 
print(find_min([3, 4, 5, 1, 2]))      # 1
print(find_min([4, 5, 6, 7, 0, 1, 2]))  # 0

Problem 8: Koko Eating Bananas (Binary Search on Answer)

LeetCode 875: Koko can eat at speed k bananas/hour. Given piles and h hours, find the minimum k.

Key insight: Binary search on the answer k. For each candidate speed, check if Koko can finish all piles in h hours.

// TypeScript - Koko Eating Bananas
function minEatingSpeed(piles: number[], h: number): number {
  let left = 1;
  let right = Math.max(...piles);
 
  while (left < right) {
    const mid = Math.floor(left + (right - left) / 2);
 
    if (canFinish(piles, mid, h)) {
      right = mid;     // Try slower speed
    } else {
      left = mid + 1;  // Need faster speed
    }
  }
 
  return left;
}
 
function canFinish(piles: number[], speed: number, hours: number): boolean {
  let totalHours = 0;
  for (const pile of piles) {
    totalHours += Math.ceil(pile / speed);
  }
  return totalHours <= hours;
}
 
console.log(minEatingSpeed([3, 6, 7, 11], 8));   // 4
console.log(minEatingSpeed([30, 11, 23, 4, 20], 5)); // 30
console.log(minEatingSpeed([30, 11, 23, 4, 20], 6)); // 23

# Python - Koko Eating Bananas
import math
 
def min_eating_speed(piles: list[int], h: int) -> int:
    left, right = 1, max(piles)
 
    while left < right:
        mid = left + (right - left) // 2
 
        if can_finish(piles, mid, h):
            right = mid      # Try slower speed
        else:
            left = mid + 1   # Need faster speed
 
    return left
 
def can_finish(piles: list[int], speed: int, hours: int) -> bool:
    total_hours = sum(math.ceil(pile / speed) for pile in piles)
    return total_hours <= hours
 
print(min_eating_speed([3, 6, 7, 11], 8))    # 4
print(min_eating_speed([30, 11, 23, 4, 20], 5))  # 30

Trace for piles=[3,6,7,11], h=8:

Search space: [1, 11]
 
mid=6: ceil(3/6)+ceil(6/6)+ceil(7/6)+ceil(11/6) = 1+1+2+2 = 6 ≤ 8 ✓ → right=6
mid=3: ceil(3/3)+ceil(6/3)+ceil(7/3)+ceil(11/3) = 1+2+3+4 = 10 > 8 ✗ → left=4
mid=5: ceil(3/5)+ceil(6/5)+ceil(7/5)+ceil(11/5) = 1+2+2+3 = 8 ≤ 8 ✓ → right=5
mid=4: ceil(3/4)+ceil(6/4)+ceil(7/4)+ceil(11/4) = 1+2+2+3 = 8 ≤ 8 ✓ → right=4
 
left=4, right=4 → return 4

Time: O(n × log(max_pile)) — binary search × feasibility check
Space: O(1)

10. Binary Search Decision Framework

Use this decision tree to identify which binary search pattern to apply:

Signal words in interview problems:

Signal	Pattern
"find target in sorted array"	Pattern 1: Standard
"first occurrence", "leftmost", "minimum that satisfies"	Pattern 2: Lower Bound
"last occurrence", "rightmost", "maximum that satisfies"	Pattern 2: Upper Bound
"minimum speed/capacity/time to achieve X"	Pattern 3: Search on Answer
"rotated sorted array"	Modified Pattern 1
"peak element"	Pattern 2 variation

11. Practice Problems

Sorting Problems

Easy:

#	Problem	Key Concept
1	Sort Colors	Dutch National Flag
2	Merge Sorted Array	Two pointers from end
3	Valid Anagram	Counting sort variant
4	Contains Duplicate	Sort + adjacent check

Medium:

#	Problem	Key Concept
5	Merge Intervals	Sort + merge
6	Kth Largest Element	Quick Select
7	Top K Frequent Elements	Bucket sort
8	Sort List	Merge sort on linked list
9	Largest Number	Custom comparator

Hard:

#	Problem	Key Concept
10	Count of Smaller Numbers	Merge sort + counting

Binary Search Problems

Easy:

#	Problem	Key Concept
1	Binary Search	Standard binary search
2	First Bad Version	Lower bound
3	Search Insert Position	Lower bound
4	Sqrt(x)	Binary search on answer

Medium:

#	Problem	Key Concept
5	Search in Rotated Array	Modified binary search
6	Find First and Last Position	Boundary search
7	Find Peak Element	Binary search on peaks
8	Find Minimum in Rotated Array	Binary search on rotation
9	Koko Eating Bananas	Search on answer
10	Capacity to Ship Packages	Search on answer
11	Search a 2D Matrix	Flatten + binary search

Hard:

#	Problem	Key Concept
12	Median of Two Sorted Arrays	Binary search on partition
13	Split Array Largest Sum	Search on answer
14	Find in Rotated Array II (with dupes)	Handle duplicates

Recommended approach: Solve all Easy problems first, then Medium. Attempt Hard only after you're comfortable with the patterns.

Summary and Key Takeaways

Sorting Algorithms:
✅ O(n log n) is the lower bound for comparison sorts — Merge Sort and Quick Sort achieve this
✅ Merge Sort: stable, guaranteed O(n log n), but needs O(n) space
✅ Quick Sort: fastest in practice, in-place O(log n) space, but O(n²) worst case
✅ Insertion Sort: best for small arrays and nearly-sorted data

Binary Search Fundamentals:
✅ Eliminates half the search space each step — O(log n) time
✅ Requires sorted or monotonic input
✅ Always use mid = left + (right - left) / 2 to avoid overflow

Binary Search Patterns:
✅ Pattern 1 (Exact match): while (left <= right), return mid when found
✅ Pattern 2 (Boundary): while (left < right), find first/last satisfying condition
✅ Pattern 3 (Search on answer): Binary search the answer space with a feasibility check

Interview Tips:
✅ "Sort first" often reduces O(n²) problems to O(n log n)
✅ Binary search on answer is the most underrated pattern — look for "minimum X to achieve Y"
✅ Know when to use left <= right vs left < right — it depends on the pattern
✅ Quick Select solves "kth element" problems in O(n) average time

What's Next?

You've now mastered two of the most fundamental algorithmic tools: sorting and binary search. These techniques appear everywhere — in array problems, tree problems, graph algorithms, and system design.

Continue the DSA series:

Next: Dynamic Programming & Greedy Algorithms — Optimal substructure, memoization, and greedy choices
Previous: Heaps & Priority Queues — Efficient min/max operations
Series Overview: Data Structures & Algorithms Roadmap

Introduction

What You'll Learn

Prerequisites

Part 1: Sorting Algorithms

1. Why Sorting Matters

2. Sorting Algorithm Classification

3. Elementary Sorting Algorithms — O(n²)

3.1 Bubble Sort

3.2 Selection Sort

3.3 Insertion Sort

4. Efficient Sorting Algorithms — O(n log n)

4.1 Merge Sort

4.2 Quick Sort

4.3 Merge Sort vs Quick Sort

5. Sorting Algorithm Comparison Summary

Built-in Sorts: What Languages Use

Part 2: Binary Search

6. Binary Search Fundamentals

6.1 How Fast is O(log n)?

6.2 Standard Binary Search

6.3 Common Binary Search Bugs

7. Binary Search Patterns

7.1 Pattern 1: Find Exact Value

7.2 Pattern 2: Find First/Last Position (Boundary Search)

7.3 Pattern 3: Binary Search on Answer (Search Space Reduction)

8. Interview Problems: Sorting

Problem 1: Sort Colors (Dutch National Flag)

Problem 2: Merge Intervals

Problem 3: Kth Largest Element

9. Interview Problems: Binary Search

Problem 4: Search in Rotated Sorted Array

Problem 5: Find First and Last Position

Problem 6: Find Peak Element

Problem 7: Minimum in Rotated Sorted Array

Problem 8: Koko Eating Bananas (Binary Search on Answer)

10. Binary Search Decision Framework

11. Practice Problems

Sorting Problems

Binary Search Problems

Summary and Key Takeaways

What's Next?

📬 Subscribe to Newsletter

💬 Comments