Breaking
Divide and conquer

# Merge sort

Merge sort is a divide and conquers and comparison-based sorting algorithm. It divide the array into subarray and conquer recursively sorting two subarrays. It combines the results into a final array.

#### Dive

Divide the problem into small subproblems.

#### Conquer

Solve the subproblem using recursive function.

#### Combine

Combine the sub solution into solution.

Merge sort can be implemented Top-down and Bottom-up. Top down merge sort split the list into sub list and sort the sub list. Finally, it merges sorted sublist into a single sorted list. Bottom up merge sort treats array of sub list and iteratively merges sub-lists back and forth between two buffers.

Merge sort uses for linked list sorting, external sorting on the tab. It is stable sort compare then other sorting algorithm.

Write a program to take the un-sorted array and sort the array using Merge sort.

## source Code

```package com.dsacode.Algorithm.sorting;

import java.util.Arrays;

public class Mergesort {

private static void merge(int arr[], int l, int m, int r) {
int i, j, k;
int n1 = m - l + 1;
int n2 =  r - m;

int[] L=new int[n1];
int[] R=new int[n2];

for(i = 0; i < n1; i++)
L[i] = arr[l + i];
for(j = 0; j < n2; j++)
R[j] = arr[m + 1+ j];

i = 0;
j = 0;
k = l;
while (i < n1 && j < n2) {
if (L[i] <= R[j]) {
arr[k] = L[i];
i++;
} else {
arr[k] = R[j];
j++;
}
k++;
}

while (i < n1)  {
arr[k] = L[i];
i++;
k++;
}

while (j < n2)  {
arr[k] = R[j];
j++;
k++;
}
}

public static 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);
}
}

public static void main(String[] args) {
int arr[] = {12, 11, 13, 5, 6, 7};

System.out.println("unsorted array before sorting : " + Arrays.toString(arr));

mergeSort(arr, 0, arr.length - 1);

System.out.println("Sorted array After Mergesort sorting : " + Arrays.toString(arr));
}
}```

## Output

```Unsorted array before sorting: [12, 11, 13, 5, 6, 7]
Sorted array After Merge sort sorting: [5, 6, 7, 11, 12, 13]```