Mergesort je stabilní řadicí algoritmus typu rozděl
a panuj s asymptotickou
složitostí . Merge sort pracuje na bázi slévání již
seřazených částí pole za pomoci dodatečného pole velikosti
.
Merge sort byl vynalezen v roce 1945 Johnem von Neumannem.
Princip
Slévání
Předpokládejme, že máme dva seznamy (A, B) seřazené v sestupném pořadí. Tyto seznamy můžeme setřídit do jediného seznamu (C) následující procedurou.
V každém kroku vždy porovnejme první prvky obou seznamů (tj. nejvyšší prvky obou seznamů) a vyberme ten vyšší. Tento nakopírujme na konec seznamu C a odstraňme jej ze seznamu původního. Tento postup opakujme tak dlouho, dokud se jeden ze seznamů nevyprázdní. Potom překopírujme zbytek druhého seznamu do C (a odstraňme překopírované prvky z původního seznamu).
Ve skutečnosti slévá merge sort vždy dvě sousední části pole. Drží si dva ukazatele, každý na první prvek seznamu a po každém porovnání přesune jeden z prvků do pomocného pole a posune příslušný ukazatel o jedno místo (címž se dostane na nový nejvyšší prvek příslušného seznamu). Poté, co zkopíruje všechny prvky obou seznamů do pomocného pole, tak celé původní pole přepíše seřazeným seznamem (pomocným polem).
Dělení
Dosud jsme nezmínili, jak algoritmus získá dvě seřazená sousední pole. Dělicí část merge sortu má na svém vstupu celé pole. Pokud je pole sudé délky, tak jej rozdělí na dvě stejně velké části. Má-li pole lichou délku, tak bude jedna část obsahovat o prvek více než druhá. V každém případě pak algoritmus nově vzniklé části dále rekurzivně dělí. V okamžiku, kdy rekurze narazí na seznamy jednotkové velikosti, tak se zastaví. Nyní má algorimus v každé větvi k dispozici dva sousední seznamy, které obsahují jeden prvek a jsou tedy triviálně seřazeny.
Řazení
Merge sort se tedy začne navracet z rekurze a při každém návratu sleje dva seznamy pomocí výše zmíněné procedury slévání. Algoritmus má jistotu, že buď slévá triviálně seřazené prvky nebo seznamy, které již byly slity. V okamžiku, kdy se merge sort plně navrátí z rekurze, tak terminuje. Pole je seřazeno od nevyšší hodnoty.
Kód
/**
* Razeni slevanim (od nejvyssiho)
* @param array pole k serazeni
* @param aux pomocne pole stejne delky jako array
* @param left prvni index na ktery se smi sahnout
* @param right posledni index, na ktery se smi sahnout
*/
public static void mergeSort(int[] array, int[] aux, int left, int right) {
if(left == right) return;
int middleIndex = (left + right)/2;
mergeSort(array, aux, left, middleIndex);
mergeSort(array, aux, middleIndex + 1, right);
merge(array, aux, left, right);
for (int i = left; i <= right; i++) {
array[i] = aux[i];
}
}
/**
* Slevani pro Merge sort
* @param array pole k serazeni
* @param aux pomocne pole (stejne velikosti jako razene)
* @param left prvni index, na ktery smim sahnout
* @param right posledni index, na ktery smim sahnout
*/
private static void merge(int[] array, int[] aux, int left, int right) {
int middleIndex = (left + right)/2;
int leftIndex = left;
int rightIndex = middleIndex + 1;
int auxIndex = left;
while(leftIndex <= middleIndex && rightIndex <= right) {
if (array[leftIndex] >= array[rightIndex]) {
aux[auxIndex] = array[leftIndex++];
} else {
aux[auxIndex] = array[rightIndex++];
}
auxIndex++;
}
while (leftIndex <= middleIndex) {
aux[auxIndex] = array[leftIndex++];
auxIndex++;
}
while (rightIndex <= right) {
aux[auxIndex] = array[rightIndex++];
auxIndex++;
}
}
/**
* Razeni slevanim (od nejvyssiho)
* @param array pole k serazeni
* @param aux pomocne pole stejne delky jako array
* @param left prvni index na ktery se smi sahnout
* @param right posledni index, na ktery se smi sahnout
*/
void mergeSort(int array[], int aux[], int left, int right) {
if (left == right) return;
int middleIndex = (left + right)/2;
mergeSort(array, aux, left, middleIndex);
mergeSort(array, aux, middleIndex + 1, right);
merge(array, aux, left, right);
for (int i = left; i <= right; i++) {
array[i] = aux[i];
}
}
/**
* Slevani pro Merge sort
* @param array pole k serazeni
* @param aux pomocne pole (stejne velikosti jako razene)
* @param left prvni index, na ktery smim sahnout
* @param right posledni index, na ktery smim sahnout
*/
void merge(int array[], int aux[], int left, int right) {
int middleIndex = (left + right)/2;
int leftIndex = left;
int rightIndex = middleIndex + 1;
int auxIndex = left;
while (leftIndex <= middleIndex && rightIndex <= right) {
if (array[leftIndex] >= array[rightIndex]) {
aux[auxIndex] = array[leftIndex++];
} else {
aux[auxIndex] = array[rightIndex++];
}
auxIndex++;
}
while (leftIndex <= middleIndex) {
aux[auxIndex] = array[leftIndex++];
auxIndex++;
}
while (rightIndex <= right) {
aux[auxIndex] = array[rightIndex++];
auxIndex++;
}
}
/**
* Razeni slevanim (od nejvyssiho)
* @param array pole k serazeni
* @param aux pomocne pole stejne delky jako array
* @param left prvni index na ktery se smi sahnout
* @param right posledni index, na ktery se smi sahnout
*/
public static void MergeSort(int[] array, int[] aux, int left, int right)
{
if (left == right) return;
int middleIndex = (left + right) / 2;
MergeSort(array, aux, left, middleIndex);
MergeSort(array, aux, middleIndex + 1, right);
Merge(array, aux, left, right);
for (int i = left; i <= right; i++)
{
array[i] = aux[i];
}
}
/**
* Slevani pro Merge sort
* @param array pole k serazeni
* @param aux pomocne pole (stejne velikosti jako razene)
* @param left prvni index, na ktery smim sahnout
* @param right posledni index, na ktery smim sahnout
*/
private static void Merge(int[] array, int[] aux, int left, int right)
{
int middleIndex = (left + right) / 2;
int leftIndex = left;
int rightIndex = middleIndex + 1;
int auxIndex = left;
while (leftIndex <= middleIndex && rightIndex <= right)
{
if (array[leftIndex] >= array[rightIndex])
{
aux[auxIndex] = array[leftIndex++];
}
else
{
aux[auxIndex] = array[rightIndex++];
}
auxIndex++;
}
while (leftIndex <= middleIndex)
{
aux[auxIndex] = array[leftIndex++];
auxIndex++;
}
while (rightIndex <= right)
{
aux[auxIndex] = array[rightIndex++];
auxIndex++;
}
}