Algorithm Note 02: Merge Sort

// merge two sorted array
void mergearray(int a[], int n, int b[], int m, int c[])
{
    int i = 0;
    int j = 0;
    int k = 0;

    while (i < n && j < m)
    {
        if (a[i] < b[j])
            c[k++] = a[i++];
        else
            c[k++] = b[j++];
    }
    while (i < n)
    	c[k++] = a[i++];
    while (j < m)
    	c[k++] = b[j++];
}

// Top-down recursive based method  

void merge_sort(int arr[], const int len)
{
	int aux[len];
	merge_sort_recursive(int arr[], int aux[], 0, len - 1);
}

void merge_sort_recursive(int arr[], int aux[], int begin, int end)
{
	int len = end - begin + 1;
	int begin1 = begin;
	int middle = begin1 + (len>>1) -1;
	int end1 = middle;
	int start2 = middle + 1;
	int end2 = end;
	merge_sort_recursive(int a[], int aux[], int begin1, int end1);
	merge_sort_recursive(int a[], int aux[], int begin2, int end2);
	int k = begin;
	while (begin1 <= end1 && begin2 <= end2)
		aux[k++] = arr[begin1] < arr[begin2] ? arr[begin1++] : arr[begin2++];
	while (begin1 <= end1)
		aux[k++] = arr[begin1++];
	while (begin2 <= end2)
		aux[k++] = arr[begin2++];
	for (k = begin; k <= end; k++)
		arr[k] = aux[k];
}

// Bottom-up iterative based method

void merge_sort_iterative(int arr[], const int len)
{
	int aux = new int[len];
	for (int seq = 1; seq < len; seq += seq)
	{
		for (int begin = 0; begin < len; begin + = seq + seq)
		{
			int begin1 = begin;
			int middle = min(begin0 + seq, len);
			int end1 = middle - 1;
			int begin2 = middle;
			int end2 = begin1 + seq + seq -1; 
			int k = begin;
			while (begin1 < end1 && begin2 < end2)
				aux[k++] = arr[begin1] < arr[begin2] ? arr[begin1++] : arr[begin2++]; 
			while (begin1 < end1)
				aux[k++] = arr[begin1++];
			while (begin2 < end2)
				aux[k++] = arr[begin2++];
		}
		for (int j = 0; j < len; j++)
			arr[j] = aux[j];
	}
}