Implement Merge Sort using C++

In this article, you will learn about a sorting algorithm that uses divide and conquer strategy to sort an array. Merge sort first divides an array into equal parts and then combines them after sorting.

A C++ Implement of Merge Sort

To understand how merge sort works, let’s consider an array called arr[] having a starting index i and ending index r. Hence, we can write the array as arr[i….r]

Now, we have to divide the array into sub-arrays. The only factor we have to consider here is that it should be smaller in size and similar to the original array. For instance, by dividing the array into two halves from the middle, we have:
arr[i …. m][m+1…. r]

After dividing the problem (array), solve these subproblems recursively.

#include<iostream>
using namespace std;

void swapping(int &a, int &b) {
   int temp;
   temp = a;
   a = b;
   b = temp;
}

void merge(int arr[], int l, int m, int r) {
   int i, j, k, left_len, right_len;
   left_len = m-l+1; right_len = r-m;
   int left_arr[left_len], right_arr[right_len];

   for(i = 0; i<left_len; i++)
      left_arr[i] = arr[l+i];
   for(j = 0; j<right_len; j++)
      right_arr[j] = arr[m+1+j];
   i = 0; j = 0; k = l;

   while(i < left_len && j<right_len) {
      if(left_arr[i] <= right_arr[j]) {
         arr[k] = left_arr[i];
         i++;
      }else{
         arr[k] = right_arr[j];
         j++;
      }
      k++;
   }
   while(i<left_len) {
      arr[k] = left_arr[i];
      i++; k++;
   }
   while(j<right_len) {
      arr[k] = right_arr[j];
      j++; k++;
   }
}
void mergeSort(int arr[], int l, int r) {

   if(l < r) {
      int m = l+(r-l)/2;
      mergeSort(arr, l, m);
      mergeSort(arr, m+1, r);
      merge(arr, l, m, r);
   }
}
int main() {

int n =5;
int arr[5] = {3,4,1,7,5};
    cout << "UnSorted Data :";
    for (int i = 0; i < n; i++) {
        cout << "\t" << arr[i];
    }
    mergeSort(arr, 0, n-1);
    cout <<endl<< "Sorted Data :";
    for (int i = 0; i < n; i++) {
        cout << "\t" << arr[i];
    }
    cout<<endl;
    return 0;
}

 

Related Articles