Merge Sort

Małgorzata Piekarska

Wstęp

Sortowanie przez łączenie lub inaczej scalanie należy do algorytmów, które wykorzystują metodę „dziel i zwyciężaj”. Złożoność algorytmu wynosi n*log n, a więc jest on znacznie wydajniejszy niż sortowanie bąbelkowe, przez wstawianie czy przez wybieranie, gdzie złożoność jest kwadratowa.

Żeby zrozumieć zasadę działania przyjrzyjmy się najpierw dwóm posortowanym tablicom:
tablica 1: 2 3 7 9 10
tablica 2: 1 3 4 8 11

Zauważmy, że możemy liniowo scalić te dwa ciągi liczb i uzyskać jedną, posortowaną tablicę postępując ze schematem:

1. Ustawiamy liczniki na początki obu posortowanych tablic,
2. Porównujemy elementy i mniejszy lub równy element jako pierwszy znajduje się w scalonej tablicy,
3. Zwiększamy licznik w tej tablicy, z której zabraliśmy element,
4. Czynność powtarzamy aż do wyczerpania danych z obu tablic, tj. kiedy oba liczniki osiągną długości tablic.

Postać rekurencyjna

Poniżej implementacja algorytmu w języku c++ (z komentarzem):

int *pom; //tablica pomocnicza, potrzebna przy scalaniu

 //scalenie posortowanych podtablic
void scal(int tab[], int lewy, int srodek, int prawy) 
{
  int i, j;
   //zapisujemy lewą częsć podtablicy w tablicy pomocniczej
  for(i = srodek + 1; i>lewy; i--) 
    pom[i-1] = tab[i-1]; 

  //zapisujemy prawą częsć podtablicy w tablicy pomocniczej
  for(j = srodek; j<prawy; j++) 
    pom[prawy+srodek-j] = tab[j+1]; 

  //scalenie dwóch podtablic pomocniczych i zapisanie ich 
  //we własciwej tablicy
  for(int k=lewy;k<=prawy;k++) 
    if(pom[j]<pom[i])
      tab[k] = pom[j--];
    else
      tab[k] = pom[i++];
}

 void sortowanie_przez_scalanie(int tab[],int lewy, int prawy)
{
  //gdy mamy jeden element, to jest on już posortowany
  if(prawy<=lewy) return; 
   //znajdujemy srodek podtablicy
  int srodek = (prawy+lewy)/2;
   //dzielimy tablice na częsć lewą i prawa
  sortowanie_przez_scalanie(tab, lewy, srodek); 
  sortowanie_przez_scalanie(tab, srodek+1, prawy);
   //scalamy dwie już posortowane tablice
  scal(tab, lewy, srodek, prawy);
}