curioso

mergesort.cpp

/*
 * program: naturalmergesort.cpp
 * Program is an implementation of a 2-way natural mergesort with the addition,
 * that it counts the number of comparisions needed by the merging-process.
 */

#include <iostream>

using namespace std;

int count; //counts comparisions, ignore it

void merge(int *, int, int, int, int *);


// naturalmergesort goes through the array, lets say [2 4 6 -5 12 3 ...]
// and takes in this example: 2 4 6 and -5 12, two sequences that are already
// in order and gives them to the function merge. merge merges these to sequences
// into one.
void naturalmergesort(int * arr, int l, int r, int* pcount){
    // arr is the array that we have to sort
    // l for left is the position we start
    // r for right is where we end
    // ignore int* pcount

    int ll, mm, rr;
    // ll is the left end of the part of the array we are going to
    // give the function merge to merge.
    // mm is the end of the first sub-sequence of the given array, that
    // is already ok'ish
    // the 2nd sequence starts at mm+1 and ends at rr
    // merge then merges these two into one

    do{
        rr = l - 1;
        // start at the beginning again after going through the
        // array once, now merging subsequences ~twice as long, but only
        // half as many

        while(rr < r){ // stay inside the original array!
            ll = rr + 1; 	// ll = start of subsequence
            mm = ll;	// end of first subsequence
            // move to the right as long as...
            while(mm < r && arr[mm+1] >= arr[mm]){
                mm++;
            }
            // first subsequence is now from ll to mm
            if(mm < r){
                rr = mm + 1;
                while(rr < r && arr[rr+1] >= arr[rr]){
                    rr++;
                }
                // second one is from mm+1 to rr
                // merge them:
                merge(arr, ll, mm, rr, pcount);
            }
            // in case we get to the end of the array with the first
            // sequence
            else{
                rr = mm;
            }
        }
    }while(ll != l); // if ll is l, the we had at most two subsequences for
    // the whole array, and those two got handled by merge
    // therefore no need to start at the beginning again
}



void merge(int * arr, int l, int m, int r, int * p2count){
    // again, ignore p2count, just a very not elegant method to count the
    // comparisions needed, because for some reason i wasnt allowed to use a
    // global variable
    // the other variables:
    // arr the original array, l the position, where the first sequence of
    // number starts, it ends at m. from m+1 to r is the second.
    // these two get merged

    int * b; // is the array where we copy the merged result
    b = new int [r-l+1]; //r-l+1 = length of the two sequences we want to
    // merge
    int h, i, j, k;
    i = l;
    j = m+1;
    k = l;
    // more variables... sorry! but below is just a very typical merge-function

    // while there are numbers left in both sequences, do ...
    while(i <= m && j <= r){
        // if the number in the left sequence is lower, copy it to the
        // array b and move the pointer i in the left sequence one to the right
        if(arr[i] <= arr[j]){
            b[k-l] = arr[i];
            i++;
        }
        // else if the number in the right sequence is lower, copy it and
        // move the pointer to the right
        else{
            b[k-l] = arr[j];
            j++;
        }
        k++;
        (*p2count)++; //ignore
    }
    // no more numbers in the left sequence, just take the right sequence now
    if(i > m){
        for(h = j; h <= r; h++){
            b[k+h-j-l] = arr[h];

        }
    }
    // no more numbers in the right sequence, copy the rest in the left one
    else{
        for(h = i; h <= m; h++){
            b[k+h-i-l] = arr[h];
        }
    }
    // copy the now sorted numbers back into the original array arr
    for(h = l; h <= r; h++){
        arr[h] = b[h-l];
    }

    delete [] b;
}


int main(){
    int count; // ignore

    // input will have the form:
    // 2 (being the number of sequences we will have to sort)
    // 10 -2 -3 1 5 14 200 6 77 99 10 (first number = how many numbers in the sequence, the rest of the numbers ARE the sequence)
    // 7 -2 0 2 3 4 -100 17000

    int t, n; // t = number of sequences to come, n = first number in the line
    // in the example above: t = 2, n = 10, later n = 7
    // read in the numbers and copy them into the array called arr
    for(cin >> t; t > 0; --t){
        count = 0;
        cin >> n;
        int * arr;
        arr = new int [n];
        for(int k = 0; k < n; k++){
            cin >> arr[k];
        }

        naturalmergesort(arr, 0, n-1, &count);

        cout << count << " " << endl; // ignore

        // output ordered sequences of numbers
        for(int i = 0; i < n; i++){
            cout << arr[i] << " ";
        }

        delete [] arr;
    }
}