Algoritmi → Sortiranje → Sortiranje objedinjavanjem (Merge Sort)

Sortiranje objedinjavanjem (Merge Sort)

Prvi korak: spajanje dva sortirana niza

Ključni deo algoritma je spajanje (objedinjavanje) dva već sortirana niza. Gledamo prve elemente oba niza, manji od njih prepisujemo u rezultat i pomeramo se dalje u nizu iz koga je uzet. Kada se jedan niz potroši, prepišemo ostatak drugog.

#include <iostream>
#include <vector>
using namespace std;

int main() {
    int n, m;
    cin >> n;
    vector<int> a(n);
    for (int &x : a) cin >> x;
    cin >> m;
    vector<int> b(m);
    for (int &x : b) cin >> x;

    vector<int> c;
    int i = 0, j = 0;
    while (i < n && j < m) {          // dok oba niza imaju elemente
        if (a[i] <= b[j]) c.push_back(a[i++]);
        else c.push_back(b[j++]);
    }
    while (i < n) c.push_back(a[i++]); // ostatak niza a
    while (j < m) c.push_back(b[j++]); // ostatak niza b

    for (int x : c) cout << x << " ";
    cout << endl;
    return 0;
}

Svaki element se prepisuje tačno jednom, pa spajanje radi u vremenu O(n + m).

Algoritam: podeli, sortiraj, spoji

1. Ako niz ima jedan element, već je sortiran (bazni slučaj rekurzije).
2. Podeli niz na levu polovinu a[l..m] i desnu a[m+1..d], gde je m = (l + d) / 2.
3. Rekurzivno sortiraj levu i desnu polovinu.
4. Spoji dve sortirane polovine.

[38 27 43 3 9 82 10]
[38 27 43 3]        [9 82 10]          deljenje
[38 27] [43 3]      [9 82] [10]
[38][27][43][3]     [9][82][10]
[27 38] [3 43]      [9 82] [10]        spajanje
[3 27 38 43]        [9 10 82]
[3 9 10 27 38 43 82]

#include <iostream>
#include <vector>
using namespace std;

vector<int> a, pom;   // pom je pomoćni niz za spajanje

void mergeSort(int l, int d) {
    if (l >= d) return;               // jedan element: već sortiran
    int m = (l + d) / 2;
    mergeSort(l, m);                  // sortiraj levu polovinu
    mergeSort(m + 1, d);              // sortiraj desnu polovinu

    // spajanje a[l..m] i a[m+1..d] u pom[l..d]
    int i = l, j = m + 1, k = l;
    while (i <= m && j <= d) {
        if (a[i] <= a[j]) pom[k++] = a[i++];
        else pom[k++] = a[j++];
    }
    while (i <= m) pom[k++] = a[i++];
    while (j <= d) pom[k++] = a[j++];
    for (k = l; k <= d; k++) a[k] = pom[k];   // vrati spojeni deo u a
}

int main() {
    int n;
    cin >> n;
    a.resize(n);
    pom.resize(n);
    for (int &x : a) cin >> x;

    mergeSort(0, n - 1);

    for (int x : a) cout << x << " ";
    cout << endl;
    return 0;
}

Video: sortiranje objedinjavanjem

U videu je postupak prikazan korak po korak na primeru.

Zašto je O(n log n)?

Niz se deli na pola sve dok delovi ne postanu dužine 1. Od n elemenata do 1 stiže se posle oko log₂ n deljenja – to je broj nivoa. Na svakom nivou spajanja se ukupno prepiše svih n elemenata. Zato je ukupan rad oko n · log₂ n.

Merge sort uvek radi O(n log n), bez obzira na raspored elemenata, ali troši dodatnu memoriju za pomoćni niz veličine n.

Primena: brojanje inverzija

Inverzija je par pozicija i < j za koji je a[i] > a[j]. Broj inverzija pokazuje koliko je niz „daleko“ od sortiranog (i jednak je broju zamena koje napravi metoda mehurića). Prebrojavanje svih parova traje O(n²), ali merge sort to radi usput:

kada pri spajanju uzimamo element iz desne polovine (a[j] < a[i]), on je manji od svih preostalih elemenata leve polovine, a[i..m]. Svaki od njih čini inverziju sa njim, pa broju inverzija dodajemo m − i + 1.

#include <iostream>
#include <vector>
using namespace std;

vector<int> a, pom;

long long brojInverzija(int l, int d) {
    if (l >= d) return 0;
    int m = (l + d) / 2;
    long long br = brojInverzija(l, m) + brojInverzija(m + 1, d);
    int i = l, j = m + 1, k = l;
    while (i <= m && j <= d) {
        if (a[i] <= a[j]) pom[k++] = a[i++];
        else {
            br += m - i + 1;          // a[j] je manji od svih a[i..m]
            pom[k++] = a[j++];
        }
    }
    while (i <= m) pom[k++] = a[i++];
    while (j <= d) pom[k++] = a[j++];
    for (k = l; k <= d; k++) a[k] = pom[k];
    return br;
}

int main() {
    int n;
    cin >> n;
    a.resize(n);
    pom.resize(n);
    for (int &x : a) cin >> x;
    cout << brojInverzija(0, n - 1) << endl;
    return 0;
}

Rezultat može biti do n(n−1)/2, pa za n = 10⁵ koristimo tip long long.

Zadaci za vežbu

Za svaki zadatak postoji primer, uputstvo i rešenje. Rešenja su provereno tačna na primerima iz teksta.

Proveri znanje