• Source 
    1.     #include <iostream>
    2.     #include <vector>
    3.     using namespace std;
    4.  
    5.     void merge(vector<int> &numbers, vector<int> &temp_numbers, int left, int mid, int right);
    6.     int l = 0, r = 0, m = 0;
    7.  
    8.     void merge_sort(vector<int> &numbers, vector<int> &temp_numbers, int left, int right){     
    9.     	int mid;	
    10.  
    11.     	if (right > left) {
    12.     		mid = (left+right)/2;
    13.     		cout << "LEFT SORT" << endl;
    14.     		l++;
    15.     		merge_sort(numbers, temp_numbers, left, mid);   
    16.     		cout << "RIGHT SORT"  << endl;
    17.     		r++;
    18.     		merge_sort(numbers, temp_numbers, mid+1, right); 
    19.     		cout << "MERGE" << endl;
    20.     		m++;
    21.     		merge(numbers, temp_numbers, left, mid+1, right);	
    22.     	}
    23.     }
    24.  
    25.     void merge(vector<int> &numbers, vector<int> &temp_numbers, int left, int mid, int right){
    26.     	int i, left_end, size, temp_pos;
    27.     	left_end = mid - 1;
    28.     	temp_pos = left;
    29.     	size = right-left + 1;
    30.  
    31.     	while ((left <= left_end) && (mid <= right)) {
    32.     		if (numbers[left] <= numbers[mid]) {
    33.     			temp_numbers[temp_pos] = numbers[left];
    34.     			temp_pos++;
    35.     			left++;
    36.     		}	
    37.     		else {
    38.     			temp_numbers[temp_pos] = numbers[mid];
    39.     			temp_pos++;
    40.     			mid++;
    41.     		}
    42.     	}
    43.     	while (left <= left_end) {
    44.     		temp_numbers[temp_pos] = numbers[left];
    45.     		left++;
    46.     		temp_pos++;
    47.     	}
    48.     	while (mid <= right) {
    49.     		temp_numbers[temp_pos] = numbers[mid];
    50.     		mid++;
    51.     		temp_pos++;
    52.     	}
    53.     	for (i = 0; i <= size; i++) {
    54.     		numbers[right] = temp_numbers[right];
    55.     		right--;
    56.     	}
    57.     }
    58.  
    59.     int main(int argc, char *argv[]) {
    60.  
    61.     	vector<int> numbers = {1, 4, 2, 19, 13, 12, 100, 45, 56};
    62.     	vector<int> temp_numbers;
    63.     	int x, n;
    64.  
    65.     	n = numbers.size();
    66.     	temp_numbers.resize(n);
    67.     	cout << "\nCount: " << n << endl << "Numbers to be sorted: ";
    68.     	for (int i = 0; i < n; i++)
    69.     		cout << numbers[i] << " ";
    70.     	cout << endl << endl << "Steps taken:\n";
    71.  
    72.     	// sort
    73.     	merge_sort(numbers, temp_numbers, 0, n-1);
    74.  
    75.     	// print
    76.     	cout << endl << "Sorted array: ";
    77.     	for (int i = 0; i < n; i++)
    78.     		cout << numbers[i] << " ";
    79.     	cout << endl << endl << "left sorts: " << l << "  right sorts: " << r << "  merges: " << m << endl;	
    80.     	return 0;
    81.     }