Mis on ühendamise sorteerimise algoritmi põhiprintsiip ja eelised?

Ühendumise sorteerimis (Merge Sort) algoritm põhineb põhimõttel "jaga ja valitse". See jagab rekursiivselt algse massiivi kaheks osaks, sorteerib iga osa ning seejärel ühendab kaks sorteeritud osa üheks sorteeritud massiiviks.

Eelised:

• Stabiilsus: säilitab võrdsete elementide järjekorra.
• Garantii tööaeg O(n log n) kõige halvemal, keskmisel ja parimal juhul.
• Sobib suurte andmehulga ja välise sorteerimise jaoks.

Näide Java keeles:

void mergeSort(int[] arr, int left, int right) {
    if (left < right) {
        int mid = (left + right) / 2;
        mergeSort(arr, left, mid);
        mergeSort(arr, mid + 1, right);
        merge(arr, left, mid, right);
    }
}

void merge(int[] arr, int left, int mid, int right) {
    // Kaks sorteeritud alam-massiivi ühendamise loogika
}