Skip to content

Instantly share code, notes, and snippets.

Embed
What would you like to do?
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; 
} 
Credits: GFG, SlackEdit
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment