й день ТАК сообщество,

Я студент CS, в настоящее время выполняю эксперимент, объединяющий MergeSort и InsertionSort. Понятно, что для определенного порога, S, InsertionSort будет иметь более быстрое время выполнения, чем MergeSort. Следовательно, путем объединения обоих алгоритмов сортировки, общее время выполнения будет оптимизировано.

Однако после многократного запуска эксперимента с использованием размера выборки 1000 и различных размеров S результаты эксперимента не дают однозначного ответа каждый раз. Вот картинка с лучшими полученными результатами (обратите внимание, что в половине случаев результат не так определен):

Теперь попробуем тот же код алгоритма с размером выборки 3500:

Наконец, попробуйте тот же код алгоритма с размером выборки 500 000 (обратите внимание, что ось Y находится в миллисекундах:

Хотя по логике Hybrid MergeSort будет быстрее, когда S <= 10, так как InsertionSort не имеет рекурсивных издержек. Однако результаты моего мини эксперимента говорят об обратном.

В настоящее время мне преподают Сложности Времени:

MergeSort: O (n log n)

сортировка вставки:

Лучший случай: θ (n)Худший случай: θ (n ^ 2)

Наконец, я нашел онлайн-источник:https://cs.stackexchange.com/questions/68179/combining-merge-sort-and-insertion-sort в котором говорится, что:

Гибридная сортировка слиянием:

Лучший вариант: θ (n + n log (n / x))В худшем случае: θ (nx + n log (n / x))

Я хотел бы спросить, есть ли результаты в сообществе CS, которые показываютокончательное доказательство того, что алгоритм гибридной слияния MergeSort будет работать лучше, чем обычный алгоритм слияния MergeSort ниже определенного порога S, и если да, то почему?

Огромное спасибо SO сообществу, это может быть тривиальный вопрос, но он действительно прояснит многие вопросы, которые у меня есть в настоящее время относительно сложности времени и прочего :)

Примечание: я использую Java для кодирования алгоритма, и время выполнения может зависеть от способа, которым java хранит данные в памяти.

Код на Java:

 public static int mergeSort2(int n, int m, int s, int[] arr){
        int mid = (n+m)/2, right=0, left=0;
        if(m-n<=s)
            return insertSort(arr,n,m);
        else
        {
            right = mergeSort2(n, mid,s, arr);
            left = mergeSort2(mid+1,m,s, arr);
            return right+left+merge(n,m,s,arr);
        }      
    }

    public static int insertSort(int[] arr, int n, int m){
        int temp, comp=0;
        for(int i=n+1; i<= m; i++){
            for(int j=i; j>n; j--){ 
                comp++;
                comparison2++;
                if(arr[j]<arr[j-1]){
                    temp = arr[j];
                    arr[j] = arr[j-1];
                    arr[j-1] = temp;
                }
                else
                    break;
            }
        }
        return comp;
    }

    public static void shiftArr(int start, int m, int[] arr){
        for(int i=m; i>start; i--)
            arr[i] = arr[i-1];     
    }

public static int merge(int n, int m, int s, int[] arr){
        int comp=0;
        if(m-n<=s)
            return 0;
        int mid = (n+m)/2;
        int temp, i=n,  j=mid+1;
        while(i<=mid && j<=m)
        {
            comp++;
            comparison2++;


            if(arr[i] >= arr[j])
            {
                if(i==mid++&&j==m && (arr[i]==arr[j]))
                    break;
                temp = arr[j];
                shiftArr(i,j++,arr);
                arr[i] = temp;
                if(arr[i+1]==arr[i]){
                   i++;
                }
            }
            i++;


        }
        return comp;
    }