Merge Sort 全链路演示 (Setup + Merge)

Merge Sort 全链路拆解

准备开始...

L[] (Temp)

R[] (Temp)

arr[] (Original)

Step: 0

int n1 = mid - left + 1; int n2 = right - mid;
int[] L = new int[n1]; int[] R = new int[n2];

for (int i=0; i<n1; ++i) L[i] = arr[left + i];
for (int j=0; j<n2; ++j) R[j] = arr[mid + 1 + j];

int i = 0, j = 0;
int k = left;

while (i < n1 && j < n2) {
if (L[i] <= R[j]) {
arr[k] = L[i]; // 取左边
i++;
} else {
arr[k] = R[j]; // 取右边
j++;
}
k++;
}

// 处理剩余元素
while (i < n1) { ... }