In this tutorial, we will learn how to implement Merge Sort in java. First, we will start by understanding the Merge Sort algorithm.
Merge Sort Algorithm
Merge Sort is another sorting algorithm that follows a Divide and Conquer algorithm approach to sort the elements in an array in ascending or descending order.
It divides the array into two halves and sorts them separately. Again the two halves are divided into separate two halves and the process keeps on going until the elements are totally separated. After that, the elements are combined together in the same steps as they were separated but while combining the elements are sorted in each steps.
When the combining step is completed we will get a fully sorted array.
Before we begin, you need to have an idea on following:
Time Complexity of Merge Sort:
- Best case:
0(n log n) - Average case:
0(n log n) - Worst case:
0(n log n)
Implementation of Merge sort in java
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 | import java.util.Arrays; public class Main { public static void main(String[] args) { int[] inputArr = { 45, 87, 11, 5, 80, 9, 02, 560, 33, 99, 1 }; System.out.println("Array before sorting: "); System.out.println(Arrays.toString(inputArr)); mergesort(inputArr); System.out.println("Array after merge sorting: "); System.out.println(Arrays.toString(inputArr)); } public static void mergesort(int[] inputArr) { mergesort(inputArr, 0, inputArr.length - 1); } private static void mergesort(int[] inputArr, int start, int end) { int mid = (start + end) / 2; if (start < end) { mergesort(inputArr, start, mid); mergesort(inputArr, mid + 1, end); } int i = 0, first = start, last = mid + 1; int[] tmp = new int[end - start + 1]; while (first <= mid && last <= end) { tmp[i++] = inputArr[first] < inputArr[last] ? inputArr[first++] : inputArr[last++]; } while (first <= mid) { tmp[i++] = inputArr[first++]; } while (last <= end) { tmp[i++] = inputArr[last++]; } i = 0; while (start <= end) { inputArr[start++] = tmp[i++]; } } } |
The output of Merge Sort Algorithm in java:
