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); } }