Skip to main content

Merge sort Implementation

 Merge sort : In merge sort we will divide the array from middle recursively  until we have only one element in sub-array. After that we will merge sub-array in ascending order.

    Time complexity for merge sort will be O(nlogn) as we are splitting the array from middle so each time it's getting half so for that  it will be log(n) and while merging we are traversing the whole array so for that it will be O(n).
     So after combining both  time complexity will be O(n)+O(logn)= O(nlogn)
     space complexity will be O(n) as we need a extra same size array to hold the unsorted array.

class MergeSort {

    public static void sort(int[] array) {
        int[] aux = new int[array.length];
        sort(array, aux, 0, array.length - 1);
    }

    private static void sort(int[] array, int[] aux, int lo, int hi) {
        if (hi <= lo) return;
        int mid = (lo + hi) / 2;
        sort(array, aux, lo, mid);
        sort(array, aux, mid + 1, hi);
        merge(array, aux, lo, mid, hi); // [lo, mid] [mid + 1, hi] => [lo, hi]
    }

    private static void merge(int[] array, int[] aux, int lo, int mid, int hi) {
        for (int i = lo; i <= hi; i++) {
            aux[i] = array[i];
        }

        int i = lo;
        int j = mid + 1;
        for (int k = lo; k <= hi; k++) {
            if (i > mid) {
                array[k] = aux[j];
                j++;
            } else if (j > hi) {
                array[k] = aux[i];
                i++;
            } else if (aux[j] < aux[i]) {
                array[k] = aux[j];
                j++;
            } else {
                array[k] = aux[i];
                i++;
            }
        }
    }

    private static void print(int[] array) {
        System.out.print("[");
        for (int i = 0; i < array.length; i++) {
            System.out.print(array[i]);
            if (i < array.length - 1) {
                System.out.print(", ");
            }
        }
        System.out.println("]");
    }

    public static void main(String[] args) {
        int[] array = {111, 80, 14, 21, 19, 31, 19, 121, 10, 190, 80, 6, 7};
        sort(array);
        print(array);
    }
}

Please have a look to the  source code of all sorting method from below link
  1. BUBBLE SORT PROGRAM
  2. SELECTION SORT PROGRAM
  3. INSERTION SORT PROGRAM
  4. MERGE SORT PROGRAM
  5. QUICK SORT PROGRAM


Labels:

Comments

Post a Comment

Popular posts from this blog

JAVA 8 FUNTIONAL INTERFACE

JAVA 8 FUNTIONAL INTERFACE  Funtional Interface :     An interface which has only one abstract method can be called a funtional interface. Comparable , Runnable , Callable all these interfaces has only one abstract method and can be consider as funtional interface.    How it works :        Once we will create a interface with one abstract method then java internally predicates the input type and based on the Interface reference it apply the logic mentioned after lambda expression    lets consider we have created an interface as below @FunctionalInterface public interface FuntionalExample { public int cal ( int a , int b) ; } And below class to test our funtional Interface. public class FuntionalInterfaceExample { public static void main (String args[]) { FuntionalExample addition=( int a , int b) -> a+b ; FuntionalExample subtraction=( int a , int b) -> a-b ; FuntionalExample multipl...
Post a Comment
Read more

Java Overview : Basic Java Overview

  JAVA BASIC OVERVIEW :  Java is high-level, class-based, robust, platform independent and object oriented programming language. Here each keyword has specific meaning which we need to understand.     How java internally works and execute our logic ?    We will need to write a file with extension .java, in which we will be writing our logics to be executed and this should be inside a class because java starts from main method of any class which is public inside the file named same as class name.    Example :  public class FirstJavaProgram {      public static void main(String[] args) {      //our logics      } }   This code should be saved in a file named as  FirstJavaProgram.java Whenever we are writing a java class, it's basically a blue print of what class has and it can do, it means characteristics  and behaviour , just like a simple real l...
Post a Comment
Read more

Singly Linked List

  Single Linked List :  In Single link list each node will have 2 parts , first part will have Data while next part will have a pointer which will keep the address of its next node, while node itself will not be aware of anything apart from its next node address. Below is sample program without Tail. In this program appending an element to link list will have time complexity as O(n) as we need to travers till end of the link list to find out the last element in link list. But if we will use Tail node along with Head then time complexity for adding an element will be O(n) but still insertion of a node after a specific node will be O(n). Sample program without Tail node. import java.io.IOException ; import java.util.Scanner ; class Node { Node next = null; int data ; public Node ( int val) { data = val ; } } class LinkList { Node head = null; public void append ( int val) { if ( head == null ) { head = new Node(val) ; ...
Post a Comment
Read more