Basic Algos

bottomup_mergesort.cpp

#include<iostream>

using namespace std;


void print_arr(int* a, int l, int r){
    for(int i=l; i<=r; i++)
        cout << a[i] << " ";
    cout << endl;
}

void copy_arr(int* src, int* dest, int from, int to){
    for(int desti=from, srci=0; desti<=to; desti++, srci++)
        dest[desti] = src[srci];
}

void merge(int* a, int left_begin, int left_end, int right_begin, int right_end){
    int left_ptr = left_begin;
    int right_ptr = right_begin;

    int* res = new int[right_end-left_begin+1];

    int sorted_count = 0;

    cout << endl << "debug:: to_sort: \t\t";
    print_arr(a, left_begin, right_end);
    cout << endl << "debug:: left: \t\t\t";
    print_arr(a, left_begin, left_end);
    cout << endl << "debug:: right: \t\t\t";
    print_arr(a, right_begin, right_end);

    while(left_ptr <= left_end && right_ptr <= right_end) {
        if(a[left_ptr] <= a[right_ptr])
            res[sorted_count++] = a[left_ptr++];
        else
            res[sorted_count++] = a[right_ptr++];
        cout << endl << "debug:: [b]sorted_till_now: \t";
        print_arr(res, 0, sorted_count-1);
    }
    while(left_ptr <= left_end) {
        res[sorted_count++] = a[left_ptr++];
        cout << endl << "debug:: [l]sorted_till_now: \t";
        print_arr(res, 0, sorted_count-1);
    }
    while(right_ptr <= right_end) {
        res[sorted_count++] = a[right_ptr++];
        cout << endl << "debug:: [r]sorted_till_now: \t";
        print_arr(res, 0, sorted_count-1);
    }

    copy_arr(res, a, left_begin, right_end);

    delete[] res;
}


void mergesort(int* a, int l, int r) {
    // if(l>=r) return;
    // mergesort(a, l, mid);
    // mergesort(a, mid+1, r);
    // merge(a, l, mid, mid+1, r);
    int size = l+r-1;
    int mid;
    for(int size_to_sort=2; size_to_sort<r-l+1; size_to_sort*=2){
        for(int i=0; i<size; i+=size_to_sort){
            mid = (size_to_sort-1)/2;
            merge(a, i, i+mid, i+mid+1, i+size_to_sort-1);
        }
    }
}


int main() {
    int a[] = {4, 5, 9, 1, 10, 25, 7, 32, 56, 21};

    int l = 0;
    int r = 10-1;

    print_arr(a, l, r);

    mergesort(a, l, r);

    print_arr(a, l, r);

    return 0;
}

mergesort.cpp

#include<iostream>

using namespace std;


void print_arr(int* a, int l, int r){
    for(int i=l; i<=r; i++)
        cout << a[i] << " ";
    cout << endl;
}

void copy_arr(int* src, int* dest, int from, int to){
    for(int desti=from, srci=0; desti<=to; desti++, srci++)
        dest[desti] = src[srci];
}

void merge(int* a, int left_begin, int left_end, int right_begin, int right_end){
    int left_ptr = left_begin;
    int right_ptr = right_begin;

    int* res = new int[right_end-left_begin+1];

    int sorted_count = 0;

    // cout << endl << "debug:: to_sort: \t\t";
    // print_arr(a, left_begin, right_end);
    // cout << endl << "debug:: left: \t\t\t";
    // print_arr(a, left_begin, left_end);
    // cout << endl << "debug:: right: \t\t\t";
    // print_arr(a, right_begin, right_end);

    while(left_ptr <= left_end && right_ptr <= right_end) {
        if(a[left_ptr] <= a[right_ptr])
            res[sorted_count++] = a[left_ptr++];
        else
            res[sorted_count++] = a[right_ptr++];
        // cout << endl << "debug:: [b]sorted_till_now: \t";
        // print_arr(res, 0, sorted_count-1);
    }
    while(left_ptr <= left_end) {
        res[sorted_count++] = a[left_ptr++];
        // cout << endl << "debug:: [l]sorted_till_now: \t";
        // print_arr(res, 0, sorted_count-1);
    }
    while(right_ptr <= right_end) {
        res[sorted_count++] = a[right_ptr++];
        // cout << endl << "debug:: [r]sorted_till_now: \t";
        // print_arr(res, 0, sorted_count-1);
    }

    copy_arr(res, a, left_begin, right_end);

    delete[] res;
}


void mergesort(int* a, int l, int r) {
    if(l>=r) return;
    int mid = (l+r)/2;
    mergesort(a, l, mid);
    mergesort(a, mid+1, r);
    merge(a, l, mid, mid+1, r);
}


int main() {
    int a[] = {4, 5, 9, 1, 10, 25, 7, 32, 56, 21};

    int l = 0;
    int r = 10-1;

    print_arr(a, l, r);

    mergesort(a, l, r);

    print_arr(a, l, r);

    return 0;
}