MergeSort

#include <iostream>
#include <time.h>

#define SIZE 3000000 // 30 million

using namespace std;

void Merge(int* L, int leftSize, int* R, int rightSize, int* A, int aSize) {
    int i, j, k;
    i = j = k = 0;
    while (i < leftSize && j < rightSize) {
        if (L[i] <= R[j]) {
            A[k] = L[i];
            i++;
        } else {
            A[k] = R[j];
            j++;
        }
        k++;
    }
    while (i < leftSize) {
        A[k] = L[i];
        i++;
        k++;
    }
    while (j < rightSize) {
        A[k] = R[j];
        j++;
        k++;
    }
}

void MergeSort(int* A, int aSize) {
    if (aSize < 2)
        return;
    int mid = aSize / 2;
    int leftSize = mid;
    int rightSize = aSize - mid;
    int* L = new int[leftSize];
    int* R = new int[rightSize];
    for (int i = 0; i < leftSize; i++) {
        L[i] = A[i];
    }
    for (int i = 0; i < rightSize; i++) {
        R[i] = A[mid + i];
    }
    MergeSort(L, leftSize);
    MergeSort(R, rightSize);
    Merge(L, leftSize, R, rightSize, A, aSize);
}

int main() {

    system("COLOR F0");

    srand(time(NULL));

    int* A = new int[SIZE];
    int min = -2;
    int max = 10;

    for (int i = 0; i < SIZE; i++) {
        A[i] = rand() % (max - min + 1) + min;
    }

    // Print unsorted list...
    /*for (int i = 0; i < SIZE; i++) {
        cout << A[i];
        if (i == SIZE - 1) {
            cout << "." << endl;
        }
        cout << ", ";
    }
    cout << endl;*/

    const clock_t begin_time = clock();
    MergeSort(A, SIZE);
    cout << float(clock() - begin_time) / CLOCKS_PER_SEC << " seconds." << endl;

    // Print sorted list...
    /*for (int i = 0; i < SIZE; i++) {
        cout << A[i];
        if (i == SIZE - 1) {
            cout << "." << endl;
        }
        cout << ", ";
    }
    cout << endl;*/

    system("PAUSE");
    return 0;
}