# C++ Program for Merge Sort

Hello Everyone!

In this tutorial, we will learn how to implement the Merge Sort Algorithm, in the C++ programming language.

To understand the Merge Sort Algorithm from scratch, we will highly recommend you to first visit our tutorial on the same, as we have covered it's step-by-step implementation, here: https://www.studytonight.com/data-structures/merge-sort

Code:

``````#include <iostream>

#include<vector>

using namespace std;

//Separate method to print the list provided by the calling method
void printElems(vector < int > list) {
int i;
int len = list.size();
for (i = 0; i < len; i++)
cout << list[i] << "  ";

}

//This method is used to merge the two individual sorted lists into a single sorted list
void merge(vector < int > & a, int low, int high, int mid) {
int i, j, k;

int c;

i = low;
k = low;
j = mid + 1;

while (i <= mid && j <= high) {
if (a[i] < a[j]) {
//copying the elements from arr a to arr c.
c[k] = a[i];
k++;
i++;
} else {
//copying the elements from arr a to arr c.
c[k] = a[j];
k++;
j++;
}
}
while (i <= mid) {
//copying the elements from arr a to arr c.
c[k] = a[i];
k++;
i++;
}
while (j <= high) {
//copying the elements from arr a to arr c.
c[k] = a[j];
k++;
j++;
}
for (i = low; i < k; i++) {
//copying remaining elements from arr c to arr a
a[i] = c[i];
}

}

//The recursive Merge Sort logic
void mergeSort(vector < int > & a, int low, int high) {
int mid;
if (low < high) {
//In Merge sort, the pivot element is always the middle element that divides the list into two equal parts
mid = (low + high) / 2;

//Calling Merge sort for the elements on the left of the pivot
mergeSort(a, low, mid);

//Calling Merge sort for the elements on the right of the pivot
mergeSort(a, mid + 1, high);

//Calling to the merge method to form a single sorted list
merge(a, low, high, mid);
}

}

int main() {
int i, num, n;

//Declaring the Vector to store the integer elements to be sorted
vector < int > v;

cout << "\n\nWelcome to Studytonight :-)\n\n\n";
cout << " =====  Program to implement the Merge Sort algo using Vectors, in CPP  ===== \n\n";

//taking input from the command line (user)
cout << " Enter the number of integers you want to sort : ";
cin >> n;
cout << "\n\n";

for (i = 0; i < n; i++) {
cout << "Enter number" << i + 1 << " :  ";
cin >> num;
v.push_back(num);

}

cout << "\n\nThe elements of the list before applying the Merge sort algorithm are : ";

//Calling the method to print the actual list
printElems(v);

//Calling the Merge sort algorithm for the entire list indexed from 0 to n-1
mergeSort(v, 0, n - 1);

cout << "\n\nThe elements of the list after applying the Merge sort algorithm are  : ";

//Calling the method to print the sorted list
printElems(v);

cout << "\n\n\n";

return 0;
}``````

Output : For any query, feel free to ask in the comments section down below!

Keep Learning : )