1
function divideAndConquer<T, R>(
2
  problem: T,
3
  isBaseCase: (problem: T) => boolean,
4
  solveBase: (problem: T) => R,
5
  split: (problem: T) => T[],
6
  merge: (results: R[]) => R,
7
): R {
8
  if (isBaseCase(problem)) return solveBase(problem);
9

10
  const subProblems = split(problem);
11
  const subResults = subProblems.map(sub =>
12
    divideAndConquer(sub, isBaseCase, solveBase, split, merge),
13
  );
14

15
  return merge(subResults);
16
}

1
function mergeSort(nums: number[]): number[] {
2
  if (nums.length <= 1) return nums;
3

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

8
  return merge(left, right);
9
}
10

11
function merge(left: number[], right: number[]): number[] {
12
  const result: number[] = [];
13
  let i = 0;
14
  let j = 0;
15

16
  while (i < left.length && j < right.length) {
17
    if (left[i] <= right[j]) result.push(left[i++]);
18
    else result.push(right[j++]);
19
  }
20

21
  return result.concat(left.slice(i), right.slice(j));
22
}

1
function quickSort(nums: number[], left = 0, right = nums.length - 1): void {
2
  if (left >= right) return;
3

4
  const pivotIndex = partition(nums, left, right);
5
  quickSort(nums, left, pivotIndex - 1);
6
  quickSort(nums, pivotIndex + 1, right);
7
}
8

9
function partition(nums: number[], left: number, right: number): number {
10
  const pivot = nums[right];
11
  let storeIndex = left;
12

13
  for (let i = left; i < right; i++) {
14
    if (nums[i] < pivot) {
15
      [nums[storeIndex], nums[i]] = [nums[i], nums[storeIndex]];
16
      storeIndex++;
17
    }
18
  }
19

20
  [nums[storeIndex], nums[right]] = [nums[right], nums[storeIndex]];
21
  return storeIndex;
22
}

1
function findKthLargest(nums: number[], k: number): number {
2
  const target = nums.length - k;
3
  let left = 0;
4
  let right = nums.length - 1;
5

6
  while (left <= right) {
7
    const pivotIndex = partition(nums, left, right);
8
    if (pivotIndex === target) return nums[pivotIndex];
9
    if (pivotIndex < target) left = pivotIndex + 1;
10
    else right = pivotIndex - 1;
11
  }
12

13
  return nums[left];
14
}

1
interface Point {
2
  x: number;
3
  y: number;
4
}
5

6
function closestPair(points: Point[]): number {
7
  points.sort((a, b) => a.x - b.x);
8

9
  function distance(a: Point, b: Point): number {
10
    return Math.hypot(a.x - b.x, a.y - b.y);
11
  }
12

13
  function solve(left: number, right: number): number {
14
    if (right - left <= 3) {
15
      let best = Infinity;
16
      for (let i = left; i <= right; i++) {
17
        for (let j = i + 1; j <= right; j++) {
18
          best = Math.min(best, distance(points[i], points[j]));
19
        }
20
      }
21
      return best;
22
    }
23

24
    const mid = (left + right) >> 1;
25
    const bestLeft = solve(left, mid);
26
    const bestRight = solve(mid + 1, right);
27
    let best = Math.min(bestLeft, bestRight);
28

29
    const strip: Point[] = [];
30
    for (let i = left; i <= right; i++) {
31
      if (Math.abs(points[i].x - points[mid].x) < best) strip.push(points[i]);
32
    }
33

34
    strip.sort((a, b) => a.y - b.y);
35
    for (let i = 0; i < strip.length; i++) {
36
      for (let j = i + 1; j < strip.length && strip[j].y - strip[i].y < best; j++) {
37
        best = Math.min(best, distance(strip[i], strip[j]));
38
      }
39
    }
40

41
    return best;
42
  }
43

44
  return solve(0, points.length - 1);
45
}