1. // Sortowanie przez scalanie (mergesort)
2. // Koszt algorytmu w ka¿dym przypadku:
3. // T(n)=n log n
4. // Marcin Krajewski
5. // www.algorytm.org
6.  
7. #include <iostream>
8. #define N 10
9.  
10. using namespace std;
11.  
12. int tab[N] ;
13. int t[N];  // Tablica pomocnicza
14.  
15. /* Scalanie dwoch posortowanych ciagow
16. tab[pocz...sr] i tab[sr+1...kon] i
17. wynik zapisuje w tab[pocz...kon] */
18. void merge(int pocz, int sr, int kon)
19. {
20. int i,j,q;
21. for (i=pocz; i<=kon; i++) t[i]=tab[i];  // Skopiowanie danych do tablicy pomocniczej
22. i=pocz; j=sr+1; q=pocz;                 // Ustawienie wskaŸników tablic
23. while (i<=sr && j<=kon) {         // Przenoszenie danych z sortowaniem ze zbiorów pomocniczych do tablicy g³ównej
24. if (t[i]<t[j])
25. tab[q++]=t[i++];
26. else
27. tab[q++]=t[j++];
28. }
29. while (i<=sr) tab[q++]=t[i++]; // Przeniesienie nie skopiowanych danych ze zbioru pierwszego w przypadku, gdy drugi zbiór siê skoñczy³
30. }
31.  
32. /* Procedura sortowania tab[pocz...kon] */
33. void mergesort(int pocz, int kon)
34. {
35. int sr;
36. if (pocz<kon) {
37. sr=(pocz+kon)/2;
38. mergesort(pocz, sr);    // Dzielenie lewej czêœci
39. mergesort(sr+1, kon);   // Dzielenie prawej czêœci
40. merge(pocz, sr, kon);   // £¹czenie czêœci lewej i prawej
41. }
42. }
43.  
44. int main() {
45. int i;
46.  
47. cout<<"Wpisz liczby"<<endl;
48. for (i=0; i<N; i++)
49.     cin>>tab[i];
50.  
51.  
52. mergesort(0,N-1);
53.  
54. cout<<"Zbior po sortowaniu: "<<endl;
55. for (i=0; i<N; i++)
56. cout<<tab[i]<<endl;
57. }
58.