Harici Sıralama ve Birleştirme (External Sorting & Merging) Algoritması

1class ReplacementSelectionSimulator {
2  static generateRuns(input: number[], memSize: number): number[][] {
3    const runs: number[][] = [];
4    let currentRun: number[] = [];
5    const heap: number[] = [];
6    const deadSpace: number[] = [];
7
8    let inputIdx = 0;
9    // Belleği doldur
10    while (inputIdx < input.length && heap.length < memSize) {
11      heap.push(input[inputIdx++]);
12    }
13    heap.sort((a, b) => a - b); // Min heap simülasyonu
14
15    while (heap.length > 0 || deadSpace.length > 0) {
16      if (heap.length === 0) {
17        // Yeni bir run başlat
18        runs.push(currentRun);
19        currentRun = [];
20        heap.push(...deadSpace);
21        deadSpace.length = 0;
22        heap.sort((a, b) => a - b);
23      }
24
25      const val = heap.shift()!;
26      currentRun.push(val);
27
28      if (inputIdx < input.length) {
29        const nextVal = input[inputIdx++];
30        if (nextVal >= val) {
31          heap.push(nextVal);
32          heap.sort((a, b) => a - b);
33        } else {
34          deadSpace.push(nextVal);
35        }
36      }
37    }
38    if (currentRun.length > 0) {
39      runs.push(currentRun);
40    }
41    return runs;
42  }
43}