{{ message }}

Instantly share code, notes, and snippets.

# nishantmendiratta/Algorithms > Sorting > Merge Sort.md

Created Sep 30, 2020
Algorithms > Sorting > Merge Sort

Merge sort is divide and conquer algorithm. It divides input array in two halves, calls itself for the two halves and then merge the two sorted sub-arrays.

``````#include <iostream>
using namespace std;

/* UTILITY FUNCTIONS */
/* Function to print an array */
void printArray(int *A, int size) {
int i;
for (i = 0; i < size; i++)
cout << A[i] << "\t";
}

void merge(int arr[], int start, int mid, int end) {
int leftArrLen = mid-start+1;
int rightArrLen = end-mid;
int L[leftArrLen], R[rightArrLen];

for (int i = 0; i < leftArrLen; i++) {
L[i] = arr[i+start];
}
for (int j = 0; j < rightArrLen; j++) {
R[j] = arr[mid+1+j];
}

int i = 0, j = 0, k = start;
while(i<leftArrLen && j<rightArrLen) {
if (L[i] < R[j]) {
arr[k] = L[i];
i++;
}else {
arr[k] = R[j];
j++;
}
k++;
}

while(i<leftArrLen) {
arr[k] = L[i];
i++;k++;
}
while(j<rightArrLen) {
arr[k] = R[j];
j++;k++;
}
}

void mergeSort(int arr[], int start, int end) {
if (start<end) {
int mid = (end+start)/2;

mergeSort(arr, start, mid);
mergeSort(arr, mid+1, end);
merge(arr, start, mid, end);
}
}

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 << "\n" << "Sorted array is" <<"\n";
printArray(arr, arr_size);
return 0;
}
``````