Sorting & Searching

Merge Sort

Divide and Conquer Approach

Merge Sort is a stable, divide-and-conquer algorithm that divides the array into halves, recursively sorts them, and then merges the sorted halves back together.

📚 Real-Life Analogy:

Think of organizing a large pile of papers by date. You split the pile in half, ask two friends to sort each half, then merge the two sorted piles by comparing the top papers from each pile.

TypeScript

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 leftIndex = 0;
    let rightIndex = 0;
    
    // Compare elements and merge in sorted order
    while (leftIndex < left.length && rightIndex < right.length) {
        if (left[leftIndex] <= right[rightIndex]) {
            result.push(left[leftIndex]);
            leftIndex++;
        } else {
            result.push(right[rightIndex]);
            rightIndex++;
        }
    }
    
    // Add remaining elements
    while (leftIndex < left.length) {
        result.push(left[leftIndex]);
        leftIndex++;
    }
    
    while (rightIndex < right.length) {
        result.push(right[rightIndex]);
        rightIndex++;
    }
    
    return result;
}

// Example usage
const unsorted = [64, 34, 25, 12, 22, 11, 90];
const sorted = mergeSort(unsorted);
console.log(sorted); // [11, 12, 22, 25, 34, 64, 90]

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(left, right):
    result = []
    left_index = 0
    right_index = 0
    
    # Compare elements and merge in sorted order
    while left_index < len(left) and right_index < len(right):
        if left[left_index] <= right[right_index]:
            result.append(left[left_index])
            left_index += 1
        else:
            result.append(right[right_index])
            right_index += 1
    
    # Add remaining elements
    while left_index < len(left):
        result.append(left[left_index])
        left_index += 1
    
    while right_index < len(right):
        result.append(right[right_index])
        right_index += 1
    
    return result

# Example usage
unsorted = [64, 34, 25, 12, 22, 11, 90]
sorted_arr = merge_sort(unsorted)
print(sorted_arr)  # [11, 12, 22, 25, 34, 64, 90]

OCaml

let rec merge_sort = function
  | [] | [_] as lst -> lst
  | lst ->
      let rec split lst acc1 acc2 = function
        | 0 -> (List.rev acc1, acc2)
        | n -> match lst with
          | [] -> (List.rev acc1, acc2)
          | h :: t -> split t (h :: acc1) acc2 (n - 1)
      in
      let len = List.length lst in
      let (left, right) = split lst [] lst (len / 2) in
      merge (merge_sort left) (merge_sort right)

and merge left right =
  let rec merge_aux acc = function
    | ([], right) -> List.rev_append acc right
    | (left, []) -> List.rev_append acc left
    | (h1 :: t1, h2 :: t2) ->
        if h1 <= h2 then
          merge_aux (h1 :: acc) (t1, h2 :: t2)
        else
          merge_aux (h2 :: acc) (h1 :: t1, t2)
  in
  merge_aux [] (left, right)

(* Example usage *)
let unsorted = [64; 34; 25; 12; 22; 11; 90]
let sorted = merge_sort unsorted
(* sorted = [11; 12; 22; 25; 34; 64; 90] *)

🎯 Key Characteristics:

Stable: Maintains relative order of equal elements
Consistent: Always O(n log n) time complexity
Divide & Conquer: Breaks problem into smaller subproblems
Space: Requires O(n) additional space

Case	Time Complexity	Space Complexity
Best	O(n log n)	O(n)
Average	O(n log n)	O(n)
Worst	O(n log n)	O(n)

Quick Sort

Partition-Based Sorting

Quick Sort selects a 'pivot' element and partitions the array so that elements smaller than the pivot come before it, and elements greater come after it. It then recursively sorts the partitions.

🎯 Real-Life Analogy:

Think of organizing people by height. You pick one person as a reference (pivot), then arrange everyone shorter to their left and everyone taller to their right. Repeat this process for each group.

TypeScript

function quickSort(arr: number[], low: number = 0, high: number = arr.length - 1): void {
    if (low < high) {
        // Partition the array and get the pivot index
        const pivotIndex = partition(arr, low, high);
        
        // Recursively sort elements before and after partition
        quickSort(arr, low, pivotIndex - 1);
        quickSort(arr, pivotIndex + 1, high);
    }
}

function partition(arr: number[], low: number, high: number): number {
    // Choose the rightmost element as pivot
    const pivot = arr[high];
    let i = low - 1; // Index of smaller element
    
    for (let j = low; j < high; j++) {
        // If current element is smaller than or equal to pivot
        if (arr[j] <= pivot) {
            i++;
            [arr[i], arr[j]] = [arr[j], arr[i]]; // Swap elements
        }
    }
    
    // Place pivot in correct position
    [arr[i + 1], arr[high]] = [arr[high], arr[i + 1]];
    return i + 1;
}

// Example usage
const numbers = [64, 34, 25, 12, 22, 11, 90];
quickSort(numbers);
console.log(numbers); // [11, 12, 22, 25, 34, 64, 90]

Python

def quick_sort(arr, low=0, high=None):
    if high is None:
        high = len(arr) - 1
    
    if low < high:
        # Partition the array and get the pivot index
        pivot_index = partition(arr, low, high)
        
        # Recursively sort elements before and after partition
        quick_sort(arr, low, pivot_index - 1)
        quick_sort(arr, pivot_index + 1, high)

def partition(arr, low, high):
    # Choose the rightmost element as pivot
    pivot = arr[high]
    i = low - 1  # Index of smaller element
    
    for j in range(low, high):
        # If current element is smaller than or equal to pivot
        if arr[j] <= pivot:
            i += 1
            arr[i], arr[j] = arr[j], arr[i]  # Swap elements
    
    # Place pivot in correct position
    arr[i + 1], arr[high] = arr[high], arr[i + 1]
    return i + 1

# Example usage
numbers = [64, 34, 25, 12, 22, 11, 90]
quick_sort(numbers)
print(numbers)  # [11, 12, 22, 25, 34, 64, 90]

OCaml

let rec quick_sort = function
  | [] -> []
  | pivot :: rest ->
      let smaller = List.filter (fun x -> x <= pivot) rest in
      let larger = List.filter (fun x -> x > pivot) rest in
      (quick_sort smaller) @ [pivot] @ (quick_sort larger)

(* Alternative in-place version using arrays *)
let quick_sort_array arr =
  let rec sort low high =
    if low < high then
      let pivot_index = partition arr low high in
      sort low (pivot_index - 1);
      sort (pivot_index + 1) high
  
  and partition arr low high =
    let pivot = arr.(high) in
    let i = ref (low - 1) in
    
    for j = low to high - 1 do
      if arr.(j) <= pivot then (
        incr i;
        let temp = arr.(!i) in
        arr.(!i) <- arr.(j);
        arr.(j) <- temp
      )
    done;
    
    let temp = arr.(!i + 1) in
    arr.(!i + 1) <- arr.(high);
    arr.(high) <- temp;
    !i + 1
  in
  sort 0 (Array.length arr - 1)

(* Example usage *)
let numbers = [|64; 34; 25; 12; 22; 11; 90|]
let () = quick_sort_array numbers
(* numbers is now [|11; 12; 22; 25; 34; 64; 90|] *)

Case	Time Complexity	Space Complexity
Best	O(n log n)	O(log n)
Average	O(n log n)	O(log n)
Worst	O(n²)	O(n)

Binary Search

Efficient Search in Sorted Arrays

Binary Search repeatedly divides a sorted array in half, comparing the target with the middle element to determine which half to search next.

📖 Real-Life Analogy:

Think of finding a word in a dictionary. You open to the middle, see if your word comes before or after, then repeat with the appropriate half until you find it.

TypeScript

function binarySearch(arr: number[], target: number): number {
    let left = 0;
    let right = arr.length - 1;
    
    while (left <= right) {
        const mid = Math.floor((left + right) / 2);
        
        if (arr[mid] === target) {
            return mid; // Found the target
        } else if (arr[mid] < target) {
            left = mid + 1; // Search right half
        } else {
            right = mid - 1; // Search left half
        }
    }
    
    return -1; // Target not found
}

// Recursive version
function binarySearchRecursive(
    arr: number[], 
    target: number, 
    left: number = 0, 
    right: number = arr.length - 1
): number {
    if (left > right) {
        return -1; // Target not found
    }
    
    const mid = Math.floor((left + right) / 2);
    
    if (arr[mid] === target) {
        return mid;
    } else if (arr[mid] < target) {
        return binarySearchRecursive(arr, target, mid + 1, right);
    } else {
        return binarySearchRecursive(arr, target, left, mid - 1);
    }
}

// Example usage
const sortedArray = [11, 12, 22, 25, 34, 64, 90];
console.log(binarySearch(sortedArray, 25)); // 3
console.log(binarySearch(sortedArray, 50)); // -1

Python

def binary_search(arr, target):
    left = 0
    right = len(arr) - 1
    
    while left <= right:
        mid = (left + right) // 2
        
        if arr[mid] == target:
            return mid  # Found the target
        elif arr[mid] < target:
            left = mid + 1  # Search right half
        else:
            right = mid - 1  # Search left half
    
    return -1  # Target not found

# Recursive version
def binary_search_recursive(arr, target, left=0, right=None):
    if right is None:
        right = len(arr) - 1
    
    if left > right:
        return -1  # Target not found
    
    mid = (left + right) // 2
    
    if arr[mid] == target:
        return mid
    elif arr[mid] < target:
        return binary_search_recursive(arr, target, mid + 1, right)
    else:
        return binary_search_recursive(arr, target, left, mid - 1)

# Example usage
sorted_array = [11, 12, 22, 25, 34, 64, 90]
print(binary_search(sorted_array, 25))  # 3
print(binary_search(sorted_array, 50))  # -1

OCaml

let binary_search arr target =
  let rec search left right =
    if left > right then -1
    else
      let mid = (left + right) / 2 in
      if arr.(mid) = target then mid
      else if arr.(mid) < target then search (mid + 1) right
      else search left (mid - 1)
  in
  search 0 (Array.length arr - 1)

(* Alternative iterative version *)
let binary_search_iterative arr target =
  let left = ref 0 in
  let right = ref (Array.length arr - 1) in
  let found = ref false in
  let result = ref (-1) in
  
  while !left <= !right && not !found do
    let mid = (!left + !right) / 2 in
    if arr.(mid) = target then (
      result := mid;
      found := true
    ) else if arr.(mid) < target then
      left := mid + 1
    else
      right := mid - 1
  done;
  !result

(* Example usage *)
let sorted_array = [|11; 12; 22; 25; 34; 64; 90|]
let index = binary_search sorted_array 25 (* Returns 3 *)
let not_found = binary_search sorted_array 50 (* Returns -1 *)

🎯 Prerequisites & Applications:

Prerequisite: Array must be sorted
Search Range: Finding insertion point for new elements
Variants: Lower bound, upper bound searches
Applications: Database indexing, finding peaks, rotated arrays

Case	Time Complexity	Space Complexity
Best	O(1)	O(1)
Average	O(log n)	O(1)
Worst	O(log n)	O(1)

Heap Sort

Heap-Based Sorting

Heap Sort builds a max heap from the array, then repeatedly extracts the maximum element and places it at the end of the sorted portion.

🏆 Real-Life Analogy:

Think of a tournament where you always know who the strongest player is. You remove the strongest, reorganize to find the next strongest, and repeat until everyone is ranked.

🎯 Key Advantages:

In-Place: Sorts with O(1) extra space
Consistent: Always O(n log n) time complexity
Not Stable: May change relative order of equal elements
Selection-Based: Good for finding k largest/smallest elements

Case	Time Complexity	Space Complexity
Best	O(n log n)	O(1)
Average	O(n log n)	O(1)
Worst	O(n log n)	O(1)

DSA Interview Guide

Sorting & Searching

🎯 Key Characteristics:

🎯 Prerequisites & Applications:

🎯 Key Advantages: