Merge Sort


  • Time Complexity - O(nLogn) || Space Complexity - O(n) [Due to two temp arrays taken to store left and right subpart]
  • It follows a divide and conquer strategy
  • It is a stable sort
  • Java 6 and below versions of Java used merge sort in for their inbuilt .sort() method
__________________________________________________________________________________________________________________________________________________________________



public class Main {
    
    public static void mergeSort(int[] arr, int left, int right){
        // if left is less than right, it means there is more than 1 element. Hence, this problem can be broken down into smaller sub-problems
        if(left<right){
            // we find the mid first and break this array into 2 parts around mid
            int mid = (left+right)/2;
            // first part
            mergeSort(arr,left,mid);
            // second part
            mergeSort(arr,mid+1,right);
            
            // now we merge the two parts
            merge(arr,left,mid,right);
        }
    }
    
    public static void merge(int[] arr, int left, int mid, int right){
        
        // take two temp arrays - left and right and copy data of left subproblem and right subproblem into these temp arrays
        int[] leftPart = new int[mid-left+1];
        int[] rightPart = new int[right-mid];
        
        // now copy data from arr to left and right temp arrays
        
        for(int i=0;i<leftPart.length;i++){
            leftPart[i] = arr[(left)+i];
        }
        
        for(int j=0;j<rightPart.length;j++){
            rightPart[j] = arr[(mid+1)+j];
        }
        
        // we will start from first element of both array- leftPart and rightPart, compare it and store the minimum into arr 
        int leftIndex = 0;
        int rightIndex = 0;
        
        int k=left;
        
        while(leftIndex<=(leftPart.length-1) && rightIndex<=(rightPart.length-1)){
            if(leftPart[leftIndex]<rightPart[rightIndex]){
                // pick element from leftPart
                arr[k]=leftPart[leftIndex];
                k++;
                leftIndex++;
            }
            else{
                //pick element from rightPart
                arr[k]=rightPart[rightIndex];
                k++;
                rightIndex++;
            }
        }
        
        // pick all leftover elements from left part (temp array), if any and add it to arr
        for(int i=leftIndex;i<leftPart.length;i++){
            arr[k]=leftPart[i];
            leftIndex++;
            k++;
        }
        
        // pick all leftover elements from right part (temp array), if any and add it to arr
        for(int i=rightIndex;i<rightPart.length;i++){
            arr[k]=rightPart[i];
            rightIndex++;
            k++;
        }
        
    }
    public static void main(String[] args) throws Exception {
        int[] arr={1,4,4,5,6,2,3,90,120,43,0};
        
        System.out.println("UnSorted Array :");
        for(int i=0;i<arr.length;i++){
            System.out.print(arr[i]+" ");
        }
        System.out.println();
        
        // merge sort
       
        mergeSort(arr,0,arr.length-1);
        
        
        System.out.println();
        System.out.println("Sorted Array in increasing order:");
        for(int i=0;i<arr.length;i++){
            System.out.print(arr[i]+" ");
        }
    }
}

Output :

UnSorted Array :
1 4 4 5 6 2 3 90 120 43 0 

Sorted Array in increasing order:
0 1 2 3 4 4 5 6 43 90 120


Comments

Post a Comment

Popular posts from this blog

Binary Heap - Introduction

Image
#Image Credit - GeeksForGeeks Types of heap: Min Heap - every node is less than or equal to  its children(s) Max Heap - every node is more than or equal to its children(s) Operations on any heap : create insert extract/delete - we can extract/delete only the top node in any heap traverse delete entire heap get size of heap peek top of heap We should prefer implementing binary heap using arrays and not linked list, as during bottom to top heapify, in reaching the bottom rightmost node we take only 0(1) time in case of array but we take 0(n) time in case of linked list because first, we need to level order traverse the binary heap tree to get bottom-most rightmost element.  Heaps are used to efficiently implement:  Prim's Algorithm Heapsort Priority queue
Read more

Divide and Conquer - Introduction

Image
What is Divide and Conquer? Divide and Conquer is an algorithm paradigm in which we break down a given problem into smaller sub-problems of similar type until the sub-problems are small enough to be solved directly. The solution to these sub-problems are then combined to give a solution to the original problem.  Study the diagram below, it will then make more sense about what we do in Divide and Conquer : Where to Apply Divide and Conquer? The Divide and Conquer can be applied to all those problems that show Optimal Substructure property.  So, What is this Optimal Substructure property now? If we can break down a problem into similar sub-problems and the solution of these sub-problems can be used to create the solution of the whole problem, then that problem is said to have the Optimal Substructure property. For eg. : Fibonacci(n) = Fibonacci(n-1) + Fibonacci(n-2),    In this example, we can see that if we want to find the Fibonacci number at the nth place, we can break this problem in
Read more

Bubble Sort

Time complexity - O(n^2)  || Space Complexity - O(1) Bubble sort is an inplace sorting algorithm, that means we do not any extra space while bubble sorting public class Main {     public static void main(String[] args) throws Exception {         int[] arr={1,4,4,5,6,2,3,90,120,43,0};                  System.out.println("UnSorted Array :");         for(int i=0;i<arr.length;i++){             System.out.print(arr[i]+" ");         }         System.out.println();         // bubble sort         for(int i=0;i<arr.length-1;i++){ // iterates through first to last cell             for(int j=0;j<arr.length-1-i;j++){ // inner loop controls swapping and extent to which swapping is to be performed in array                 if(arr[j]>arr[j+1]){                     int temp = arr[j];                     arr[j]=arr[j+1];                     arr[j+1]=temp;                 }             }             // after each iteration we ge
Read more