### merge sort

###########################
####    merge sort     ####
###########################

- split the input in half. split each of the sub-group in half again.
- recursively split until you reach only two elements, then compare and swap them.

e.g.          // assume we are sorting in the ascending order

input = {6,5,4,3,2,1}

{6,5,4}{3,2,1}
(6,5){4}{3,2}{1}   // depends on how you split the odd number, but either way is fine.
{6}{5}{4}{3}{2}{1}
{5,6}{4}{2,3}{1}   // now we treat each of both {5,6} and {4} as array (even tho {4} is a single elem)
// in this case, we first prepare a temp array of size 3.
// then we compare the top elem from each array, and start putting the smaller one into the temp array.
// so, {4}, then {4,5} then {4,5,6}.   similarly for {2,3}{1} pair
{4,5,6}{1,2,3}     // now lets do it for the last pair
// {1}       after 4 > 1
// {1,2}     after 4 > 2
// {1,2,3}   after 4 > 3
// the rest is automatic
{1,2,3,4,5,6}

========> can easily be a recursive implementation.

- a stable sort

(ref)
http://en.wikipedia.org/wiki/Merge_sort
http://ppp-lab.sakura.ne.jp/ProgrammingPlacePlus/algorithm/sort/007.html

####################################
####   computation complexity   ####
####################################

worst case   :  O(n log n)
best case    :  O(n log n)
average case :  O(n log n)

it's splitting the input half, and half, and half, like a binary search. so the loop(depth) is O(log n).
and each phase of the loop, you just iterate thru every elem(compare), so it is O(N).

thus in total, worst case is O(n log n).

and this logic is persistent regardless of the input data pattern. thus it's always O(n log n).

###############################
####   space complexity    ####
###############################

total     : O(N)
auxiliary : O(N)   // for we use a temp array to copy the input. this is not good.
// but we can make it O(1)  if LL is used.

##########################################
####   implementation example (C++)   ####
##########################################

there are two ways to go about it. (1)top-down (2)bottom-up

-----------------------(top down)------------------------  // main.cpp

#include <iostream>
using namespace std;

void mergeSort(int* arr, int arrSize)

if(arrSize == 1)
return;
int mid = arrSize/2;
if(arrSize%2 == 1)
mid++;
mergeSort(arr,mid);                  // recursively splits the input in half, and mergeSort on each of the sub array
mergeSort(arr + mid,arrSize-mid);

int temp[arrSize];                   // here you allocate a temp arr to merge two arrays. thus auxiliary space complexity O(N)
for(int i=0; i < mid ;i++)
temp[i] = arr[i];
for(int i=mid; i < arrSize; i++)
temp[i] = arr[i];

int j = 0;
for(int i=0; i < arrSize ;i++)
{
if( j == mid ){                 // if the right side array is depleted, simply copy the top(smallest) elem from the left side array
arr[i] = temp[mid];
mid++;
}
else if(mid == arrSize){        // if the left side array is depleted, simpy copy the top elem from the rigth side array
arr[i] = temp[j];
j++;
}
else if( temp[j] > temp[mid])    // this will not move the val to the front if equal val, making this a stable sort.
{
arr[i] = temp[mid];
mid++;
}
else
{
arr[i] = temp[j];
j++;
}
}

void printArr(int* arr, int arrSize)

for(int i = 0; i < arrSize ; i++)
cout << arr[i] << " ";
cout << endl;

int main()

int arr[] = {92,11,8,44,32,81,56,7,22,11,-9};

int arrSize = sizeof(arr)/sizeof(arr[0]);

printArr(arr,arrSize);               // 92 11 8 44 32 81 56 7 22 11 -9
mergeSort(arr,arrSize);
printArr(arr,arrSize);               // -9 7 8 11 11 22 32 44 56 81 92

return 0;

----------------------------------------------------------

-------------------------(bottom-up)---------------------- // main.cpp

#include <iostream>
using namespace std;

int min(int a, int b)

if(b < a)
return b;
else
return a;

void mergeSort(int* arr, int arrSize)

if(arrSize <= 1 )
return;

int temp[arrSize];

for(int i=2;  ; i *= 2 )    // since it's bottom up, comparison is 2,4,8,,  2^n (n>0)    NOTE: we allow i = arrSize
{
if(i >= 2*arrSize)       // break condition is a bit confusing, but we want to allow i=8 when arrSize=5, so when i=16, then we break.
break;                 // or we also break when i=8 and arrSize=4, still allowing i=arrSize
for(int n = 0; n < arrSize; n += i)   // this is the loop for gonig thru all sub arrays we merge
{
int mid = n + i/2;          // just taking the mid index between arr[n] and arr[n+i].  (n+(n+i))/2 = n+i/2

for(int k = n; k < mid ; k++)
temp[k] = arr[k];
for(int h = mid; h < min(n+i,arrSize) ; h++)
temp[h] = arr[h];

int j = n;

for(int m=n; m < min(n+i,arrSize) ;m++)      // this is the merge loop where we split each array into two, and compare/merge them.
{
if( j == mid ){                 // if the right side array is depleted, simply copy the top(smallest) elem from the left side array
arr[m] = temp[mid];
mid++;
}
else if(mid == min(n+i,arrSize)){ // if the left side array is depleted, simpy copy the top elem from the rigth side array
arr[m] = temp[j];
j++;
}
else if( temp[j] > temp[mid])    // this will not move the val to the front if equal val, making this a stable sort.
{
arr[m] = temp[mid];
mid++;
}
else
{
arr[m] = temp[j];
j++;
}
}

}
}

void printArr(int* arr, int arrSize)

for(int i = 0; i < arrSize ; i++)
cout << arr[i] << " ";
cout << endl;

int main()

int arr[] = {92,11,8,44,32,81,56,7,22,11,-9};

int arrSize = sizeof(arr)/sizeof(arr[0]);

printArr(arr,arrSize);               // 92 11 8 44 32 81 56 7 22 11 -9
mergeSort(arr,arrSize);
printArr(arr,arrSize);               // -9 7 8 11 11 22 32 44 56 81 92

return 0;

-------------------------------------------------------

1. 2014-06-08 14:31:31 |
2. Category : algo
3. Page View: