¿Cómo hacer que Mergesort realice comparaciones O (n) en el mejor de los casos?

Como sabemos, Mergesort es un algoritmo de divide y vencerás que divide la array en mitades recursivamente hasta que alcanza una array del tamaño de 1, y luego combina las subarreglas ordenadas hasta que la array original está completamente ordenada. La implementación típica de la ordenación por fusión funciona en tiempo O(n Log n) en los tres casos (mejor, promedio y peor).

Necesitamos reducir el rendimiento del mejor caso de O(n log n) a O(n).

La idea es considerar el caso cuando la array ya está ordenada. Antes de fusionar, solo verifique si arr[mid] > arr[mid+1], porque estamos tratando con subarreglos ordenados. Esto nos llevará a la relación recursiva T(n) = 2*T(n/2) + 1 que puede resolverse mediante el teorema del maestro , por lo que T(n) = n.

Ejemplos:

Input : 1 2 3 4
Subarrays with size of 1:|1||2| |3||4|
Subarrays with size of 2: |1 2| |3 4|
Output : 1 2 3 4

Input : 1 2 3 4 5 6 7 8 
        Subarrays with size of 1: |1||2| |3||4| |5||6| |7||8|
        Subarrays with size of 2: |1 2| |3 4| |5 6| |7 8|
        Subarrays with size of 4: |1 2 3 4| |5 6 7 8|
Output : 1 2 3 4 5 6 7 8 

// C program to implement merge sort that works
// in O(n) time in best case.
#include <stdio.h>
#include <stdlib.h>
  
void merge(int* arr, int low, int mid, int high);
  
void mergesort(int* arr, int low, int high)
{
    if (low < high) {
        int mid = (low + high) / 2;
        mergesort(arr, low, mid);
        mergesort(arr, mid + 1, high);
  
        // This is where we optimize for best
        // case.
        if (arr[mid] > arr[mid + 1])
            merge(arr, low, mid, high);
    }
}
  
void merge(int* arr, int low, int mid, int high)
{
    int i = low, j = mid + 1, k = 0;
    int* temp = (int*)calloc(high - low + 1, sizeof(int));
    while ((i <= mid) && (j <= high))
        if (arr[i] < arr[j])
            temp[k++] = arr[i++];
        else
            temp[k++] = arr[j++];
    while (j <= high) // if( i>mid )
        temp[k++] = arr[j++];
    while (i <= mid) // j>high
        temp[k++] = arr[i++];
  
    // copy temp[] to arr[]
    for (i = low, k = 0; i <= high; i++, k++)
        arr[i] = temp[k];
    free(temp);
}
  
int main()
{
    int a[] = { 1, 2, 3, 4, 5, 6, 7, 8 };
    mergesort(a, 0, 7);
    for (int i = 0; i < 8; i++)
        printf("%d ", a[i]);
    return 0;
}

Producción:

 1 2 3 4 5 6 7 8

Este artículo es una contribución de Shlomi Elhaiani . Si le gusta GeeksforGeeks y le gustaría contribuir, también puede escribir un artículo usando contribuya.geeksforgeeks.org o envíe su artículo por correo a contribuya@geeksforgeeks.org. Vea su artículo que aparece en la página principal de GeeksforGeeks y ayude a otros Geeks.

Escriba comentarios si encuentra algo incorrecto o si desea compartir más información sobre el tema tratado anteriormente.