Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <iostream>
- #include <fstream>
- #include <algorithm>
- using namespace std;
- // Complexitate: O(nlogn)
- int t[1001];
- void merge_sort(int v[], int st, int dr)
- {
- if(st == dr)
- return;
- int mid, i, j, k;
- mid = (st + dr) / 2;
- merge_sort(v, st, mid);
- merge_sort(v, mid+1, dr);
- // vrem sa interclasam vectorul v[st], v[st+1], ..., v[mid]
- // si vectorul v[mid+1], v[mid+2], ..., v[dr]
- i = st;
- j = mid+1;
- k = 1;
- while(i <= mid && j <= dr)
- {
- if(v[i] < v[j])
- {
- t[k] = v[i];
- i++;
- }
- else
- {
- t[k] = v[j];
- j++;
- }
- k++;
- }
- while(i <= mid)
- {
- t[k] = v[i];
- i++;
- k++;
- }
- while(j <= dr)
- {
- t[k] = v[j];
- j++;
- k++;
- }
- // t[1], t[2], t[3], ..., t[k-1] -> v[st], v[st+1], v[st+2], ..., v[dr]
- for(int i = 1; i < k; i++)
- v[st+i-1] = t[i];
- /* merge(v+st, v+mid+1, v+mid+1, v+dr+1, t+1);
- for(int i = 1; i <= dr-st+1; i++)
- v[st+i-1] = t[i];*/
- }
- int main()
- {
- int n, v[1001];
- cin >> n;
- for(int i = 1; i <= n; i++)
- cin >> v[i];
- merge_sort(v, 1, n);
- for(int i = 1; i <= n; i++)
- cout << v[i] << " ";
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement