### Merge Sort Algorithm - The Coding Shala

Last Updated: 20-Jan-2021
Home >> Algorithms >> Merge Sort Algorithm

In this post, we will learn what is Merge Sort Algorithm and how it works. We will write a Java Program for Merge Sort.

## Merge Sort Algorithm

Merge Sort is an efficient and general-purpose sorting algorithm. It is a classic example of the divide-and-conquer algorithm.

The merge sort algorithm can be divided into three steps, like all the divide-and-conquer algorithm:

step 1. Divide the given unsorted list into several sublists. (Divide)

step 2. Sort each of the sublists recursively. (Conquer)

Step 3. Merge the sorted sublists to produce a new sorted list. (Combine)

Here is an example that explains the working of the merge sort algorithm:

#### The time complexity of Merge Sort Algorithm

The time complexity of the merge sort algorithm is O(NlogN), where N is the length of the input list.

## Merge Sort Algorithm Java Program

Java Program:

```import java.util.Arrays;

//merger sort
//the coding shala

class Main{

public static int[] merge_sort(int[] input) {
int len = input.length;
if(len<=1) return input;

int mid = len/2;
//divide into left and right array by mid
int[] left = merge_sort(Arrays.copyOfRange(input, 0, mid));
int[] right = merge_sort(Arrays.copyOfRange(input, mid, len));

//merge both arrays
return merge(left, right);
}

public static int[] merge(int[] left, int[] right) {
int len_left = left.length;
int len_right = right.length;
int[] result = new int[len_left+len_right];

int left_index = 0, right_index = 0, result_index = 0;
//combine the arrays in order
while(left_index < len_left && right_index < len_right) {
if(left[left_index] < right[right_index]) {
result[result_index] = left[left_index];
result_index++;
left_index++;
}else {
result[result_index] = right[right_index];
result_index++;
right_index++;
}
}

//if left array elements remains
while(left_index < len_left) {
result[result_index] = left[left_index];
result_index++;
left_index++;
}

//if right array element remains
while(right_index < len_right) {
result[result_index] = right[right_index];
result_index++;
right_index++;
}

return result;
}

public static void main(String[] args) {
int[] input = {1,5,3,2,8,7,6,4};
input = merge_sort(input);
for(int i=0;i<input.length;i++) {
System.out.print(input[i]+" ");
}
}
}
```

Other Posts You May Like