Tags:
create new tag
view all tags

Recursion

Merge sort

#include <iostream>
#include <vector>
using namespace std;
 
void display(vector<int> a);
void merge(vector<int> &a, int s, int e);
void merge_sort(vector<int> &iArray, int s, int e);

//The main function
int main() {
    vector<int> iArray = {45,2,5,12,78,34,18,93,1,47,32,37,7};
    merge_sort(iArray, 0, iArray.size() - 1);
    //Print the sorted array
    display(iArray);
    return 0;
}
 
// Display a vector of ints
void display(vector<int> a) {
    for (int i = 0; i < a.size(); i++) {
        cout << a[i] << " ";
    }
    cout << endl;
}

void add(vector<int> a, int s, int e, vector<int> &b) {
    for (int i=s;i<=e;i++) {
        b.push_back(a[i]);
    }
}
// The merge function
void merge(vector<int> &a, int s, int e) {
    vector<int> b;
    int m=(s+e)/2;
    int i=s;
    int j=m+1;
    while ((i<=m) && (j<=e)) {
        if (a[i]<=a[j]) {
            b.push_back(a[i++]);
        } else {
            b.push_back(a[j++]);
        }
    }
    // copy the rest
    if (i<=m) add(a,i,m,b);
    if (j<=e) add(a,j,e,b);

    // Copy back into a
    int k=s;
    for (int i=0;i<b.size(); i++) {
        a[k]=b[i];
        k++;
    }
    
}

//The recursive merge sort function
void merge_sort(vector<int> &a, int s, int e) {
    if (s>=e) return;
    int m=(s+e)/2;
    merge_sort(a,s,m);
    merge_sort(a,m+1,e);
    merge(a,s,e);
}
Topic revision: r1 - 2017-12-05 - JimSkon
 
This site is powered by the TWiki collaboration platform Powered by PerlCopyright © 2008-2018 by the contributing authors. All material on this collaboration platform is the property of the contributing authors.
Ideas, requests, problems regarding TWiki? Send feedback