Sortare prin Interclasare (Merge Sort) în C++

Principiul Divide et Impera

Merge Sort împarte recursiv vectorul în două jumătăți, le sortează separat, apoi le interclasează.

Implementare

Copiază
1#include <iostream>
2#include <vector>
3using namespace std;
4
5void interclasare(vector<int>& v, int st, int mid, int dr) {
6    vector<int> temp;
7    int i = st, j = mid + 1;
8    
9    while (i <= mid && j <= dr) {
10        if (v[i] <= v[j]) {
11            temp.push_back(v[i++]);
12        } else {
13            temp.push_back(v[j++]);
14        }
15    }
16    
17    while (i <= mid) temp.push_back(v[i++]);
18    while (j <= dr) temp.push_back(v[j++]);
19    
20    for (int k = 0; k < temp.size(); k++) {
21        v[st + k] = temp[k];
22    }
23}
24
25void mergeSort(vector<int>& v, int st, int dr) {
26    if (st < dr) {
27        int mid = st + (dr - st) / 2;
28        mergeSort(v, st, mid);
29        mergeSort(v, mid + 1, dr);
30        interclasare(v, st, mid, dr);
31    }
32}
33
34int main() {
35    vector<int> v = {64, 34, 25, 12, 22, 11, 90};
36    
37    cout << "Vector initial: ";
38    for (int x : v) cout << x << " ";
39    cout << endl;
40    
41    mergeSort(v, 0, v.size() - 1);
42    
43    cout << "Vector sortat: ";
44    for (int x : v) cout << x << " ";
45    cout << endl;
46    
47    return 0;
48}

Complexitate

Avantaje și Dezavantaje

Avantaje:

• •Complexitate garantată O(n log n)
• •Stabil (păstrează ordinea relativă a elementelor egale)
• •Potrivit pentru liste înlănțuite

Dezavantaje:

• •Necesită memorie suplimentară O(n)
• •Nu este in-place