Patterns

Split into smaller subproblems, solve recursively, combine results

When to useMerge sort, quick sort, find majority element, max subarray (D&C version)

recursive

BASE CASE

single element / trivial input → return directly

if (left === right) return arr[left];

if (nums.length <= 1) return nums;

DIVIDE

split input into halves

const mid = Math.floor((left + right) / 2);

const mid = Math.floor(nums.length / 2);
const left = mergeSort(nums.slice(0, mid));
const right = mergeSort(nums.slice(mid));

RECURSE

recursively solve each half

const leftMax = helper(arr, left, mid);
const rightMax = helper(arr, mid + 1, right);

// (left and right are the recursively sorted halves)

[COMBINE]

merge subresults into final answer

return Math.max(leftMax, rightMax);

return merge(left, right);
// merge: while placing left[l], smallerArr[left[l][0]] += r