MergeSortArrayAccessCountTrial

main.cpp

#include <iostream>
#include <vector>
#include <random>
#include <cmath>
#include "mergesortTop.h"
#include "mergesortUp.h"
using namespace std;
 
random_device rd;
mt19937 e(rd());
uniform_int_distribution<int> dist(INT16_MIN, INT16_MAX);

int main(){
	// cout << "i\t" << "access count\t" << "6NlgN" << endl;
	for(int i = 1; i <= 512; i++){
		vector<int> a(i);
		vector<int> aux(i);
		unsigned TopDownCnt = 0;
		// unsigned BottomUpCnt = 0;

		for(int j = 0; j < i ; j++){
			a[j] = dist(e);
		}
		// MergeTopDown::sort(a, aux, TopDownCnt);
		MergeBottomUp::sort(a, aux, TopDownCnt);

		// cout << i << "\t"
			// cout << TopDownCnt << "\t"
			 cout << static_cast<int>(6*i*log2(i))
			 << endl;
	}
	return 0;
}

mergesortTop.h

#pragma once
#include <vector>
#include <iostream>
class MergeTopDown{
    public:
        static void sort(std::vector<int> &a, std::vector<int> &aux, unsigned &count){
            count = 0;

            sort(a, aux, 0, a.size() - 1, count);
        }
    private:    
        static void sort(std::vector<int> &a, std::vector<int> &aux, int lo, int hi, unsigned &count){
            if(hi <= lo) return;
            int mid = lo + (hi - lo) / 2;
            sort(a, aux, lo, mid, count);
            sort(a, aux, mid+1, hi, count);
            merge(a, aux, lo, mid, hi, count);
        }
        static void merge(std::vector<int> &a, std::vector<int> &aux, int lo, int mid, int hi, unsigned &count){
            int i = lo, j = mid+1;
            for(int k = lo; k <= hi; k++){
                aux[k] = a[k];
                count += 2;
            }

            for(int k = lo; k <= hi; k++){
                if(i > mid){
                   a[k] = aux[j++]; 
                }else if (j > hi){
                    a[k] = aux[i++];
                }else if(aux[i] < aux[j]){
                    a[k] = aux[i++];
                    count += 2;
                }else{
                    a[k] = aux[j++];
                    count += 2;
                }
                count += 2;
            }
        }
};

mergesortUp.h

#pragma once
#include <algorithm>
#include <vector>
class MergeBottomUp{
    public:
        static void sort(std::vector<int> &a, std::vector<int> &aux, int lo, int hi, unsigned &count){
            if(hi <= lo) return;
            int mid = lo + (hi - lo) / 2;
            sort(a, aux, lo, mid, count);
            sort(a, aux, mid+1, hi, count);
            merge(a, aux, lo, mid, hi, count);
        }

        static void sort(std::vector<int> &a, std::vector<int> &aux, unsigned &count){
            int length = a.size();
            for(int sz = 1; sz < length; sz = sz + sz){
                for(int lo = 0; lo < length - sz; lo += sz + sz){
                    merge(a, aux, lo, lo + sz - 1, std::min(lo+sz+sz-1, length-1), count);
                }
            }
        }

        static void merge(std::vector<int> &a, std::vector<int> &aux, int lo, int mid, int hi, unsigned &count){
            int i = lo, j = mid+1;
            for(int k = lo; k <= hi; k++){
                aux[k] = a[k];
                count += 2;
            }

            for(int k = lo; k <= hi; k++){
                if(i > mid){
                   a[k] = aux[j++]; 
                }else if (j > hi){
                    a[k] = aux[i++];
                }else if(aux[i] < aux[j]){
                    a[k] = aux[i++];
                    count += 2;
                }else{
                    a[k] = aux[j++];
                    count += 2;
                }
                count += 2;
            }
        }
};