diff options
author | Santo Cariotti <santo@dcariotti.me> | 2021-02-06 19:56:36 +0100 |
---|---|---|
committer | Santo Cariotti <santo@dcariotti.me> | 2021-02-06 19:56:36 +0100 |
commit | d2edbc38cac8da52f58c5cd3da6c0c625fa05736 (patch) | |
tree | a51e9a4e56fc9d4c7c9e37576dceedca3a0c72b4 /Year_1/Programming_2/algorithms/mergesort.cc | |
parent | 98f34040820dc3a964b7be59a698323e8cc6c8a3 (diff) |
conf: rename
Diffstat (limited to 'Year_1/Programming_2/algorithms/mergesort.cc')
-rw-r--r-- | Year_1/Programming_2/algorithms/mergesort.cc | 52 |
1 files changed, 52 insertions, 0 deletions
diff --git a/Year_1/Programming_2/algorithms/mergesort.cc b/Year_1/Programming_2/algorithms/mergesort.cc new file mode 100644 index 0000000..68d28cb --- /dev/null +++ b/Year_1/Programming_2/algorithms/mergesort.cc @@ -0,0 +1,52 @@ +#include<iostream> + +using namespace std; + +void merge(int A[], int l, int q, int r) { + int i = l; + int j = q+1; + int k = l; + int B[r]; + + while((i <= q) && (j <= r)) { + if(A[i] <= A[j]) + B[k] = A[i++]; + else + B[k] = A[j++]; + + k++; + } + + while(i <= q) + B[k++] = A[i++]; + + while(j <= r) + B[k++] = A[j++]; + + for(k = l; k <= r; ++k) + A[k] = B[k]; +} + +void mergesort(int A[], int l, int r) { + if(l < r) { + int q = (l+r)/2; + mergesort(A, l, q); + mergesort(A, q+1, r); + merge(A, l, q, r); + } +} + + +int main() { + int a[] = {7,1,22,3,2,12,27,31,6}; + for(int i = 0; i < 9; ++i) { + cout << a[i] << ' '; + } + cout << endl; + mergesort(a, 0, 8); + for(int i = 0; i < 9; ++i) { + cout << a[i] << ' '; + } + + return 0; +} |