Java:合并排序是 O(N^2) 还是 O(N Log(N))

Question

我创建了自己的归并排序实现，并测试了它是否有效。我怎么不确定它是应该的 O(N Log(N)) 还是 O(N^2)，你能看看我的代码并告诉我吗？

排序列表

public abstract class SortedList {
    public final ArrayList<Integer> params = new ArrayList<Integer>();

    public void add(int... params) {
        for (int parameter : params) {
            this.params.add(parameter);
        }
    }

    abstract public void sort();

    public void print() {
        for (int parameter : params) {
            System.out.print(parameter + " ");
        }
        System.out.println();
    }
}

MargeSort

public class MargeSort extends SortedList{

    private int buffer[];

    @Override
    public void sort() {
        buffer = new int[params.size()];
        for(int i = 1; i < params.size(); i *= 2){
            sort(i);
        }
    }

    private void sort(int interval) {
        for(int i = 0; i < params.size() - interval; i += interval * 2){
            sort(i, i + interval, interval);
        }
    }

    private void sort(int index1, int index2, int interval) {
        int startingIndex = index1;
        int index1MaxValue = index1 + interval;
        int index2MaxValue = index2 + interval;
        if(index2MaxValue >= params.size()){
            index2MaxValue = params.size();
        }
        int counter = 0;

        for(counter = 0; index1 < index1MaxValue && index2 < index2MaxValue; counter++){
            int param1 = params.get(index1);
            int param2 = params.get(index2);
            if(param1 < param2){
                buffer[counter] = param1;
                index1++;
            }
            else{
                buffer[counter] = param2;
                index2++;
            }
        }
        int index, indexMaxValue;
        if(index1 < index1MaxValue){
            index = index1;
            indexMaxValue = index1MaxValue;
        }
        else{
            index = index2;
            indexMaxValue = index2MaxValue;
        }

        while(index < indexMaxValue){
            int param = params.get(index);
            buffer[counter] = param;
            index++;
            counter++;
        }

        for(int i = 0; i < interval * 2 && i + startingIndex < params.size(); i++){
            params.set(i + startingIndex, buffer[i]);
        }
    }
}

Answer 1

sort(int) 被调用 lg N 次，其中 N = params.size()。 [lg N 在这里和所有地方进一步意味着 ceil(lg N)]

Loop in sort(int) 循环 N/(interval/2) 次，其中 interval in [1 .. lgN]，调用 sort(...)，这需要 nr 个步骤，它是线性的取决于它的 interval arg。

所以，nr 个步骤是:

Sigma(k in from 1 to lgN): (N/(interval/2)) * (C * interval) = C * N/2 * Sigma(1..lgN) 1 = C * N * lgN/2

[ C 是计算内部sort(...) 成本的常量]