Buen día comunidad SO,

Soy un estudiante de CS que actualmente realiza un experimento que combina MergeSort e InsertionSort. Se entiende que para un cierto umbral, S, InsertionSort tendrá un tiempo de ejecución más rápido que MergeSort. Por lo tanto, al combinar ambos algoritmos de clasificación, se optimizará el tiempo de ejecución total.

Sin embargo, después de ejecutar el experimento muchas veces, utilizando un tamaño de muestra de 1000 y tamaños variables de S, los resultados del experimento no dan una respuesta definitiva cada vez. Aquí hay una imagen de los mejores resultados obtenidos (tenga en cuenta que la mitad de las veces el resultado no es tan definitivo):

Ahora, probando el mismo código de algoritmo con un tamaño de muestra de 3500:

Finalmente, intente el mismo código de algoritmo con un tamaño de muestra de 500,000 (Tenga en cuenta que el eje y está en milisegundos:

Aunque lógicamente, el Hybrid MergeSort será más rápido cuando S <= 10, ya que InsertionSort no tiene tiempo de carga recursivo. Sin embargo, los resultados de mi mini experimento dicen lo contrario.

Actualmente, estas son las complejidades del tiempo que me enseñaron:

MergeSort: O (n log n)

Tipo de inserción:

Mejor caso: θ (n)Peor caso: θ (n ^ 2)

Finalmente, he encontrado una fuente en línea:https://cs.stackexchange.com/questions/68179/combining-merge-sort-and-insertion-sort eso dice que:

Hybrid MergeInsertionSort:

Mejor caso: θ (n + n log (n / x))Peor caso: θ (nx + n log (n / x))

Me gustaría preguntar si hay resultados en la comunidad CS que muestrenprueba definitiva de que un algoritmo MergeSort híbrido funcionará mejor que un algoritmo MergeSort normal por debajo de cierto umbral, S, y si es así, por qué?

Muchas gracias a la comunidad SO, puede ser una pregunta trivial, pero realmente aclarará muchas preguntas que tengo actualmente sobre Complejidades de tiempo y otras cosas :)

Nota: Estoy usando Java para la codificación del algoritmo, y el tiempo de ejecución podría verse afectado por la forma en que Java almacena los datos en la memoria.

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