Merge sort

O(n log n) — Linearithmic Time

syntax

Typical of efficient comparison-based sorts. You divide (log n levels) and do O(n) work per level.

example

// JavaScript
// Merge sort achieves O(n log n) guaranteed
const sorted = [5, 2, 8, 1, 9].sort((a, b) => a - b);
// Built-in sort: V8 uses TimSort → O(n log n)

# Python
# Python's sorted() uses TimSort → O(n log n)
result = sorted([5, 2, 8, 1, 9])
# list.sort() is in-place, also O(n log n)

output

Time: O(n log n) | Space: O(n) for merge sort, O(log n) for quicksort avg

Note O(n log n) is the theoretical lower bound for comparison-based sorting. If an interviewer asks you to do better, the input must have special structure (e.g., bounded integers for counting sort). Heap operations on n elements also yield O(n log n).

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.

DSAInterview Prep