﻿ C++ Merge Sort ~ Programming Tutorials by SourceTricks
Friday, June 17, 2011

## C++ Merge Sort

### What is Merge Sort algorithm? How to implement Merge Sort in C++?

• Merge Sort  is a divide and conquer algorithm.
• In the best/ average/ worst case it gives a time complexity of O(n log n).
Conceptually, a merge sort works as follows:
1. If the list is of length 0 or 1, then it is already sorted. Otherwise:
2. Divide the unsorted list into two sublists of about half the size.
3. Sort each sublist recursively by re-applying the merge sort.
4. Merge the two sublists back into one sorted list.
(Reference: http://en.wikipedia.org/wiki/Merge_sort)

### Demonstrate a simple merge sort implementation

``````#include <iostream>
#include <cmath>
using namespace std;

const int INPUT_SIZE = 10;

// A simple print function
void print(int *input)
{
for ( int i = 0; i < INPUT_SIZE; i++ )
cout << input[i] << " ";
cout << endl;
}

void merge(int* input, int p, int r)
{
int mid = floor((p + r) / 2);
int i1 = 0;
int i2 = p;
int i3 = mid + 1;

// Temp array
int temp[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];
}

void merge_sort(int* input, int p, int r)
{
if ( p < r )
{
int mid = floor((p + r) / 2);
merge_sort(input, p, mid);
merge_sort(input, mid + 1, r);
merge(input, p, r);
}
}

int main()
{
int input[INPUT_SIZE] = {500, 700, 800, 100, 300, 200, 900, 400, 1000, 600};
cout << "Input: ";
print(input);
merge_sort(input, 0, 9);
cout << "Output: ";
print(input);
return 0;
}
```
```
OUTPUT:-
``````
Input: 500 700 800 100 300 200 900 400 1000 600
Output: 100 200 300 400 500 600 700 800 900 1000
``````

Name

Email *

Message *