Get this book -> Problems on Array: For Interviews and Competitive Programming

In this article at OpenGenus, we will learn how to design and implement Merge Sort in C++ Programming Language in detail using OOP concepts.

# Definition:

**Merge Sort** is a sorting algorithm that sorts an array of elements using the **Divide-and-Conquer** approach. To create a sorted array, the algorithm splits the array in two, sorts each half individually, and then merges the two halves back together.

**Figure showing the recursive Merge Sort**

# Algorithm:

Merge Sort is a Divide and Conquer Algorithm.

**Steps to perform the Merge Sort:**

- We will divide the given unsorted array into two halves of equal size.
- Then, we will recursively sort the first and second half.
- After sorting two halves, we will merge them to get the required sorted array.

## Implementation of the Merge Sort Algorithm using Object-Oriented Programming(OOP):

In this implementation, the **MergeSort class** contains a public member function, **mergeSort** and a private member function, **merge**.

The **merge()** function is specified as private member function in the merge sort implementation because they are only used within the **MergeSort** class. This function carry out the fundamental operation of the merge sort algorithm, but because they are not visible to outside callers, they are not concerned with the algorithm's inner working.

On the other hand, a merge sort implementation uses a public member function to offer an interface for calling the sorting algorithm from outside code. Because it is the function that external code will call to sort an array of integers, the **mergeSort()** function in the MergeSort class is specified as a public member function.

Following is the structure of the MergeSort Class:

```
class MergeSort{
public:
void mergeSort{
//array is divided into two halves and sorted recursively
}
private:
void merge{
//two sorted halves gets merge into a single sorted array
}
};
```

From the point of user, we can use this class as follows:

```
MergeSort mSort;
mSort.mergeSort(arr, 0, n-1);
```

The **mergeSort()** function first divides the array into two halves and then recursively sorts them and calls the **merge()** function. When the base case of a single element is reached, the two halves are merged together using the private **merge()** function. The **merge()** function is a helper function that merges two sorted sub-arrays.

We use a vector **temp** in the implementation of merge sort in C++ because it provides several advantages such as:

- Vectors in C++ are dynamic arrays that can be resized at runtime and it is useful for merge sort because the size of the input array can vary depending on the input data.
- It is safer to use because they automatically handle memory allocation and deallocation.
- It also supports random access, which means that we can access any element in the array in constant time.

```
class MergeSort
{
public:
void mergeSort(int arr[], int l, int r)
{
//l and r are the starting and ending index of the unsorted array
if(l >= r) return;
//mid is the index which divides the array into two almost equal halves
int mid = (l+r)/2;
//to sort the left half
mergeSort(arr, l, mid);
//to sort the right half
mergeSort(arr, mid+1, r);
//to merge the two sorted halves
merge(arr,l,mid,r);
}
private:
void merge(int arr[], int l, int m, int r)
{
int left = l;
int right = m+1;
//to store the sorted elements
vector<int> temp;
while(left <= m && right <= r){
if(arr[left] <= arr[right]){
temp.push_back(arr[left]);
left++;
}else{
temp.push_back(arr[right]);
right++;
}
}
while(left <= m){
temp.push_back(arr[left]);
left++;
}
while(right <= r){
temp.push_back(arr[right]);
right++;
}
for(int i = l;i <= r;i++){
arr[i] = temp[i-l];
}
}
};
int main(){
int n;
cin>>n;
int arr[n];
for(int i = 0;i < n;i++){
cin>>arr[i];
}
MergeSort mSort;
mSort.mergeSort(arr, 0, n-1);
for(int i = 0;i < n;i++){
cout<<arr[i]<<" ";
}
return 0;
}
```

**Output:**

```
6
7 6 13 11 10 2 //Unsorted array
2 6 7 10 11 13 //Sorted array
```

# Time Complexity:

The divide step takes O(logn) time, since the array is divided into halves recursively until there is only one element in each sub-array. The merge step takes O(n) time, since each element of the array is compared and merged into a new array.

**Best Case Complexity**- It occurs when the array is already sorted. The best-case time complexity of merge sort is O(n*logn).**Average Case Complexity**- It occurs when the array elements are neither arranged in ascending nor descending order. The average case time complexity of merge sort is O(n*logn).**Worst Case Complexity**- It occurs when the array elements are in descending order. The worst-case time complexity of merge sort is O(n*logn).

# Space Complexity:

In Merge Sort algorithm, during merging, we create a temporary array to store the two sorted halves.

Therefore, the **space complexity** of Merge Sort is O(n), where n is the number of elements in the array being sorted.

With this article at OpenGenus, you must have the complete idea of how to implement Merge Sort in C++ Programming Language.