В книге "Алгоритмы на java" написано, что нисходящая(рекурсивная) и восходящая(итеративная) сортировки слиянием выполняет максимум 6N*lg(N) (логарифм двоичный) обращений к массиву. В одном из упражнений предлагается проверить это нарисовав график зависимости количества обращений к массиву от N . С нисходящей сортировкой все хорошо, но вот восходящая дает странные результаты.
Вот график для N = 1..512. Красная линия это 6N*lg(N), а черная фактические обращения к массиву.
Как видно в некоторых местах черная линия внезапно возрастает. Я заметил что это часто происходит при N = 2^x + 1.
Не понимаю в чем проблема, вот мой код(реализация самой сортировки полностью из книги):
public class MergeBUCount {
private static Integer count; // переменная для счета обращений к массиву
private static void merge(Comparable[] a, Comparable[] aux, int lo, int mid, int hi) {
for (int k = lo; k <= hi; k++) {
aux[k] = a[k];
count += 2; //по два обращения к массиву
}
int i = lo, j = mid+1;
for (int k = lo; k <= hi; k++) {
if (i > mid) {a[k] = aux[j++]; count += 2;}
else if (j > hi) {a[k] = aux[i++]; count += 2;}
else if (less(aux[j], aux[i])) {a[k] = aux[j++]; count += 4;}//обращения при сравнении + копировании
else {a[k] = aux[i++]; count += 4;}
}
}
public static void sort(Comparable[] a, int size) {
int N = size;
Comparable[] aux = new Comparable[N];
for (int n = 1; n < N; n = n+n) {
for (int i = 0; i < N-n; i += n+n) {
int lo = i;
int m = i+n-1;
int hi = Math.min(i+n+n-1, N-1);
merge(a, aux, lo, m, hi);
}
}
}
public static void main(String[] args) {
Integer[] a = new Integer[N];
//инициализация и тд...
for (int i = 1; i <= N; i++) {
StdRandom.shuffle(a); //перемешиваем массив
count = 0;
sort(a, i);
double limit = 6 * i * (Math.log(i) / Math.log(2)); //граничное значение
StdDraw.setPenColor(StdDraw.BLACK);
StdDraw.point(i, count); //фактическая точка
StdDraw.setPenColor(StdDraw.RED);
StdDraw.point(i, limit); //граничная точка
}
}
Простой
