TypeScriptsorting.ts
Copy
1
// Merge Sort — stable, O(n log n), O(n) space
2
function mergeSort(arr: number[]): number[] {
3
  if (arr.length <= 1) return arr;
4
  const mid = Math.floor(arr.length / 2);
5
  const left = mergeSort(arr.slice(0, mid));
6
  const right = mergeSort(arr.slice(mid));
7
  return merge(left, right);
8
}
9
 
10
function merge(a: number[], b: number[]): number[] {
11
  const result: number[] = [];
12
  let i = 0, j = 0;
13
  while (i < a.length && j < b.length) {
14
    result.push(a[i] <= b[j] ? a[i++] : b[j++]);
15
  }
16
  return result.concat(a.slice(i), b.slice(j));
17
}
18
 
19
// Quick Sort — in-place, O(n log n) avg, O(n²) worst
20
function quickSort(arr: number[], lo = 0, hi = arr.length - 1): void {
21
  if (lo >= hi) return;
22
  const pivot = partition(arr, lo, hi);
23
  quickSort(arr, lo, pivot - 1);
24
  quickSort(arr, pivot + 1, hi);
25
}
26
 
27
function partition(arr: number[], lo: number, hi: number): number {
28
  const pivot = arr[hi];
29
  let i = lo - 1;
30
  for (let j = lo; j < hi; j++) {
31
    if (arr[j] <= pivot) [arr[++i], arr[j]] = [arr[j], arr[i]];
32
  }
33
  [arr[i + 1], arr[hi]] = [arr[hi], arr[i + 1]];
34
  return i + 1;
35
}
36
 
37
// Test
38
const arr = [64, 34, 25, 12, 22, 11, 90];
39
console.log(mergeSort([...arr]));      // [11, 12, 22, 25, 34, 64, 90]
40
const q = [...arr]; quickSort(q); console.log(q); // same