Sorting

Merge sort

Pinterest LinkedIn Tumblr

Merge sort is a divide and conquer and comparison-based sorting algorithm. It divide the array into subarray and conquer by recursively sorting two subarrays. It combines the results into the 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 the Top-down or Bottom-up approach. Top down merge sort split the list into sub list and sort the sub list. Finally, it merge sorted sublist into 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 another 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 position to divide an array into two halves.
Sort the first half of elements recursively. Sort the second half of elements recursively.
Merge the first and second half sorted array.
Return the sorted array.

Time Complexity

Best CaseAverage CaseWorst Case
O(n log(n))O(n log(n))O(n log(n))

Reference

  1. http://algs4.cs.princeton.edu/22mergesort/
  2. http://en.wikipedia.org/wiki/Merge_sort
  3. http://www.ee.ryerson.ca/~courses/coe428/sorting/mergesort.html
  4. http://www.personal.kent.edu/~rmuhamma/Algorithms/MyAlgorithms/Sorting/mergeSort.htm

Write A Comment