Following C code is the implementation of merge sort, with the time complexity of O(nlogn). It was used in my current project to sort 148 million integers. At first I used bubbled sort, which took me hours to have the 148M integers sorted, because the time complexity of bubble sort is O(n^2). After replacing the sorting algorithm with merge sort, the time of sorting reduced to less than 10 mins. Amazing improvement! Although I have heard of the importance of sorting/searching algorithm for years, it was the first time I realize the magic of algorithms.

The merge sort below was found in Internet. Sorry that I forgot to record the hyperlink of the webpage. Only a few changes were made by me.

`void Merge(int* input, long p, long r)`

{

long mid = floor((p + r) / 2);

long i1 = 0;

long i2 = p;

long i3 = mid + 1;

```
``` // Temp array

int* temp=new int[r-p+1];

// Merge in sorted form the 2 arrays

while ( i2 <= mid && i3 <= r )

if ( input[i2] < input[i3] )

temp[i1++] = input[i2++];

else

temp[i1++] = input[i3++];

// Merge the remaining elements in left array

while ( i2 <= mid )

temp[i1++] = input[i2++];

// Merge the remaining elements in right array

while ( i3 <= r )

temp[i1++] = input[i3++];

// Move from temp array to master array

for ( int i = p; i <= r; i++ )

input[i] = temp[i-p];

delete [] temp;

}

`// inputs:`

// p - the start index of array input

// r - the end index of array input

void Merge_sort(int* input, long p, long r)

{

if ( p < r )

{

long mid = floor((p + r) / 2);

Merge_sort(input, p, mid);

Merge_sort(input, mid + 1, r);

Merge(input, p, r);

}

}