- /*
- * merge-sort.cpp
- *
- * Created on: 23 Aug
- * Author: lucascordeiro
- */
- #include <iostream>
- #include <math.h>
- #include <limits.h>
- using namespace std;
- void merge(int A[], int p, int q, int r)
- {
- int i, j, k, n1, n2;
- n1=q-p+1;
- n2=r-q;
- int L[n1+1], R[n2+1];
- for(i=0; i<n1; i++)
- L[i]=A[p+i];
- for(j=0; j<n2; j++)
- R[j]=A[q+j+1];
- L[n1]=INT_MAX;
- R[n2]=INT_MAX;
- i=0;
- j=0;
- for(k=p; k<=r; k++)
- {
- if (L[i]<=R[j])
- {
- A[k]=L[i];
- i++;
- }
- else
- {
- A[k]=R[j];
- j++;
- }
- }
- }
- void merge_sort(int A[], int p, int r)
- {
- int q;
- if (p<r)
- {
- q=ceil((p+r)/2);
- merge_sort(A,p,q);
- merge_sort(A,q+1,r);
- merge(A,p,q,r);
- }
- }
- int main()
- {
- int n=5;
- int A[]={5,4,1,3,2};
- #if 1
- cout << "before" << endl;
- for(int i=0; i<n; i++)
- {
- cout << "A[" << i << "]=" << A[i] << endl;
- }
- #endif
- merge_sort(A,0,n-1);
- #if 1
- cout << "after" << endl;
- for(int i=0; i<n; i++)
- {
- cout << "A[" << i << "]=" << A[i] << endl;
- }
- #endif
- return 0;
- }
Recent Pastes