It is a sorting algorithm that follows the divide-and-conquer approach. It efficiently sorts an array or a list by dividing it into smaller sub-arrays, sorting them, and then merging them back together.
C++ Code
#include <bits/stdc++.h> using namespace std; void merge(int array[], int const left, int const mid, int const right){ int const subArrayOne = mid - left + 1; int const subArrayTwo = right - mid; auto *leftArray = new int[subArrayOne], *rightArray = new int[subArrayTwo]; for (auto i = 0; i < subArrayOne; i++) leftArray[i] = array[left + i]; for (auto j = 0; j < subArrayTwo; j++) rightArray[j] = array[mid + 1 + j]; auto indexOfSubArrayOne = 0, indexOfSubArrayTwo = 0; int indexOfMergedArray = left; while (indexOfSubArrayOne < subArrayOne && indexOfSubArrayTwo < subArrayTwo) { if (leftArray[indexOfSubArrayOne] <= rightArray[indexOfSubArrayTwo]) { array[indexOfMergedArray] = leftArray[indexOfSubArrayOne]; indexOfSubArrayOne++; } else { array[indexOfMergedArray] = rightArray[indexOfSubArrayTwo]; indexOfSubArrayTwo++; } indexOfMergedArray++; } while (indexOfSubArrayOne < subArrayOne) { array[indexOfMergedArray] = leftArray[indexOfSubArrayOne]; indexOfSubArrayOne++; indexOfMergedArray++; } while (indexOfSubArrayTwo < subArrayTwo) { array[indexOfMergedArray] = rightArray[indexOfSubArrayTwo]; indexOfSubArrayTwo++; indexOfMergedArray++; } delete[] leftArray; delete[] rightArray; } void mergeSort(int array[], int const begin, int const end) { if (begin >= end) return; int mid = begin + (end - begin) / 2; mergeSort(array, begin, mid); mergeSort(array, mid + 1, end); merge(array, begin, mid, end); } void printArray(int A[], int size) { for (int i = 0; i < size; i++) cout << A[i] << " "; cout << endl; } int main() { int arr[] = { 12, 11, 13, 5, 6, 7 }; int arr_size = sizeof(arr) / sizeof(arr[0]); cout << "Given array is \n"; printArray(arr, arr_size); mergeSort(arr, 0, arr_size - 1); cout << "\nSorted array is \n"; printArray(arr, arr_size); return 0; } 
Top comments (2)
bitssubdirectory are for the implementation, not user code. Just include the correct headers.std::vector, not raw C++ arrays.autois inconsistent.Thank You for the feedback. I'll keep these things in mind for my next post. I am actually learning C++, so that's why these small mistakes happen. I'll try to reduce these mistakes in the future.