implement merge sort using divide and conquer approach-programmingraja

 Aim:Write a program to implement merge sort using divide and conquer approach.

Software used: Dev C++

Description: 

Merge sort is a sorting technique based on divide and conquer technique. 

Merge sort first divides the array into equal halves and then combines them in a sorted manner.The merge() function is used for merging two halves. 

We always need sorting with effective complexity. Here, a problem is divided into multiple sub-problems. Each sub-problem is solved individually. Finally, sub-problems are combined to form the final solution.

void mergesort(int a[], int low, int high)

Merge sort uses the following algorithm. Let the array be {53,25,40,15,26,10,14}

1. First, calculate the middle index of the array, which divides the array into two halves.

2. Call the merge sort for the first half. mergesort(a, low, middle);

3. Call the merge sort for the second half. mergesort(a, middle + 1, high);

4. Merge the two arrays in steps 2 and 3 with the help of the merge function.merge(a, low, middle, high);

Program coding: 

#include <iostream>

using namespace std;

voidmergearrays(int a[], int low, int mid, int high) 

{

int i = low, j = mid + 1, index = low, temp[100], k;

while ((i <= mid) && (j <= high))

 {

if (a[i] < a[j]) {

temp[index] = a[i];

i++;

    } else {

temp[index] = a[j];

j++;

    }

index++;

  }

if (i > mid) {

while (j <= high) {

temp[index] = a[j];

j++;

index++;

    }

  } else 

  {

while (i <= mid) {

temp[index] = a[i];

i++;

index++;

    }

  }

for (k = low; k < index; k++) 

  {

a[k] = temp[k];

  }

}

voidmergesort(int a[], int low, int high) {

if (low < high) {

int middle = (low + high) / 2; 

mergesort(a, low, middle); 

mergesort(a, middle + 1, high); 

mergearrays(a, low, middle, high);

  }

}

int main() {

int n = 7;

int a[100] = {53,25,40,15,26,10,14};

mergesort(a, 0, 6);

for (int i = 0; i < n; i++) {

cout<< a[i] << " ";

  }

}

Output: