31 lines
980 B
Java
31 lines
980 B
Java
package strategy;
|
|
|
|
import java.util.Arrays;
|
|
|
|
public class MergeSort implements SortStrategy {
|
|
@Override
|
|
public void sort(int[] data) {
|
|
System.out.println(" [MergeSort] O(n log n) — stable, good for large datasets");
|
|
mergeSort(data, 0, data.length - 1);
|
|
}
|
|
|
|
private void mergeSort(int[] a, int l, int r) {
|
|
if (l >= r) return;
|
|
int m = (l + r) / 2;
|
|
mergeSort(a, l, m); mergeSort(a, m + 1, r);
|
|
merge(a, l, m, r);
|
|
}
|
|
|
|
private void merge(int[] a, int l, int m, int r) {
|
|
int[] left = Arrays.copyOfRange(a, l, m + 1);
|
|
int[] right = Arrays.copyOfRange(a, m + 1, r + 1);
|
|
int i = 0, j = 0, k = l;
|
|
while (i < left.length && j < right.length)
|
|
a[k++] = left[i] <= right[j] ? left[i++] : right[j++];
|
|
while (i < left.length) a[k++] = left[i++];
|
|
while (j < right.length) a[k++] = right[j++];
|
|
}
|
|
|
|
@Override public String getName() { return "MergeSort"; }
|
|
}
|