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]
Algorithm Explanation
![]() | Take unsorted array as input. Find the middle point to divide the array into two halves. |
![]() | Sort the first half of elements using recursively. |
![]() | Sort the second half of elements using recursively. |
![]() | Merge the first half sorted array and second half sorted array. |
![]() | Return the sorted array. |
Time Complexity
Best Case | Average Case | Worst Case |
---|---|---|
O(n log(n)) | O(n log(n)) | O(n log(n)) |