Mean, Median, Mode

3m.cpp

// Mean medium and mode
#include <iostream>
#include <algorithm>
#include <iterator>
#include <vector>
#include <map>
using namespace std;

// This is a variant of merge sort that does mode counts and sums all the items.
template <typename InputIterator, typename OutputIterator, typename ValueType, typename SumType> void mergesort(InputIterator start, InputIterator end, OutputIterator output, SumType &sum, map<ValueType, int> &mode){
    int size = end-start;

    if (size == 1){
        // Oh, base case
        *output = *start;
        
        // OK onward to our mean and mode calculation
        sum += *start;

        if (mode.find(*start) == mode.end()){
            mode[*start] = 1;
        }
        else
            mode[*start]++;
        return;
    }

    // Split
    int split = size/2;

    // Sort Left
    mergesort(start, start+split,output, sum, mode);
    // Sort Right
    mergesort(start+split, end, output+split, sum, mode);

    // Merge in place - O(n)
    inplace_merge (output, output+split, output+size);
}

bool modeCompare(pair<int, int> left, pair<int, int> right){
    return left.second < right.second;
}

int main (){
    const int count = 21;
    int input[] = {5,10,15,20,25,50,40,30,20,10,9524,878,17,1,-99,18785,3649,-3,164,94, 10};
    int *output;        // Sorted array
    map<int, int> modeCount;
    long sum = 0;

    output = new int[count];

    mergesort(input, input+count, output, sum, modeCount);

    // Mean
    int mean = (int) ( sum / (long) count );

    int median;
    //Get median
    if (count % 2 == 0){
        median = (input[count/2] + input[count/2 - 1])/2;
    }
    else{
        median = input[count/2];
    }

    // o(n)
    map<int, int>::iterator mode = max_element(modeCount.begin(), modeCount.end(), modeCompare);

    cout << "Mean: " << mean << endl;
    cout << "Median: " << median << endl;
    cout << "Mode: " << (*mode).first << endl;
    delete[] output;
    return 0;
}