Bom dia comunidade,

Eu sou um estudante de CS atualmente realizando um experimento combinando MergeSort e InsertionSort. Entende-se que, para um determinado limite, S, InsertionSort terá um tempo de execução mais rápido que o MergeSort. Portanto, ao mesclar os dois algoritmos de classificação, o tempo de execução total será otimizado.

No entanto, depois de executar o experimento várias vezes, usando um tamanho de amostra de 1000 e tamanhos variados de S, os resultados do experimento não fornecem uma resposta definitiva a cada vez. Aqui está uma imagem dos melhores resultados obtidos (observe que na metade do tempo o resultado não é tão definitivo):

Agora, tentando o mesmo código de algoritmo com um tamanho de amostra de 3500:

Por fim, tentando o mesmo código do algoritmo com um tamanho de amostra de 500.000 (observe que o eixo y está em milissegundos:

Embora logicamente, o Hybrid MergeSort seja mais rápido quando S <= 10, pois o InsertionSort não possui tempo de sobrecarga recursivo. No entanto, os resultados do meu mini experimento dizem o contrário.

Atualmente, estas são as Complexidades de Tempo ensinadas para mim:

MergeSort: O (n log n)

InsertionSort:

Melhor caso: θ (n)Pior caso: θ (n ^ 2)

Finalmente, eu encontrei uma fonte online:https://cs.stackexchange.com/questions/68179/combining-merge-sort-and-insertion-sort que afirma que:

Hybrid MergeInsertionSort:

Melhor caso: θ (n + n log (n / x))Pior caso: θ (nx + n log (n / x))

Gostaria de perguntar se existem resultados na comunidade de CS que mostramprova definitiva de que um algoritmo Hybrid MergeSort funcionará melhor que um algoritmo MergeSort normal abaixo de um certo limite, S e, se sim, por que?

Muito obrigado comunidade SO, pode ser uma pergunta trivial, mas realmente esclarecerá muitas perguntas que atualmente tenho sobre complexidade de tempo e outras coisas :)

Nota: Estou usando Java para a codificação do algoritmo e o tempo de execução pode ser afetado pela maneira como o java armazena dados na memória.

Código em 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;
    }