Header Ads Widget

Responsive Advertisement

Merge sort of Each step how it is working

Kartik Chandra Mandal February 15, 2016

 

 In computer science, merge sort (also commonly spelled as mergesort) is an efficient, general-purpose, and comparison-based sorting algorithm. Most implementations produce a stable sort, which means that the relative order of equal elements is the same in the input and output. Merge sort is a divide-and-conquer algorithm that was invented by John von Neumann in 1945.[2] A detailed description and analysis of bottom-up merge sort appeared in a report by Goldstine and von Neumann as early as 1948


java

package com.kartik.sorting;
import com.kartik.sorting.tree.BTreePrinter;
/**
 *
 * @author MandalKC
 *
 */
public class MergeSort {
 private int[] array;
    private int[] tempMergArr;
    private int length;

    public static void main(String a[]){
        
        int[] inputArr = {45,23,11,89,77,98,4,28,65,43};
       MergeSort mms = new MergeSort();
        mms.sort(inputArr);
    }
    private void printNumbers(int[] input) {
  for (int i = 0; i < input.length; i++) {
   System.out.print(input[i] + ", ");
   } System.out.println("\n");
  }
    public void sort(int inputArr[]) {
     System.out.println("Before merge Soring --->>");
  printNumbers(inputArr);
  System.out.println("After merge Soring start--->>");
        this.array = inputArr;
        this.length = inputArr.length;
        this.tempMergArr = new int[length];
        doMergeSort(0, length - 1);
    }

    private void doMergeSort(int lowerIndex, int higherIndex) {
        
        if (lowerIndex < higherIndex) {
            int middle = lowerIndex + (higherIndex - lowerIndex) / 2;
            // Below step sorts the left side of the array
            doMergeSort(lowerIndex, middle);
            // Below step sorts the right side of the array
            doMergeSort(middle + 1, higherIndex);
            // Now merge both sides
            mergeParts(lowerIndex, middle, higherIndex);
        }
    }

    private void mergeParts(int lowerIndex, int middle, int higherIndex) {

        for (int i = lowerIndex; i <= higherIndex; i++) {
            tempMergArr[i] = array[i];
        }
        int i = lowerIndex;
        int j = middle + 1;
        int k = lowerIndex;
        while (i <= middle && j <= higherIndex) {
            if (tempMergArr[i] <= tempMergArr[j]) {
                array[k] = tempMergArr[i];
                i++;
            } else {
                array[k] = tempMergArr[j];
                j++;
            }
            k++;
            BTreePrinter.printNode(HeapSort.drawTree(array));
            printNumbers(array);
        }
        while (i <= middle) {
            array[k] = tempMergArr[i];
            k++;
            i++;
            BTreePrinter.printNode(HeapSort.drawTree(array));
            printNumbers(array);
        }

    }
}

 The provided code implements the Merge Sort algorithm in Java and includes a main method to test the sorting process. The code sorts an array of integers and prints the array before and after sorting. Additionally, it visualizes the array as a binary tree after each merge step, using BTreePrinter and HeapSort.drawTree methods.

Explanation of the Code:

  1. Variables:
    • array: The array to be sorted.
    • tempMergArr: A temporary array used during the merge process.
    • length: The length of the array.
  2. Main Method:
    • Initializes an array of integers.
    • Calls the sort() method to sort the array.
  3. Sorting Process:
    • The sort() method initializes the required variables and calls doMergeSort() to start the merge sort process.
    • The doMergeSort() method recursively divides the array into two halves until each subarray contains a single element.
    • The mergeParts() method merges the divided subarrays back together in sorted order.
  4. Printing and Visualization:
    • The printNumbers() method prints the elements of the array.
    • The code uses BTreePrinter.printNode(HeapSort.drawTree(array)) to visualize the array as a binary tree after each merge operation.

Important Notes:

  • Custom Classes: The code refers to custom classes BTreePrinter and HeapSort, which are not provided. These classes are presumably responsible for drawing and printing the array as a binary tree. You need to ensure these classes are implemented and available in your project.
  • Visualization: The array visualization as a binary tree during the merge process is an additional feature that helps in understanding the sorting process. It may not be essential for the core sorting functionality but is useful for educational purposes.

Example Output:

If you run the code, the output will look something like this:

plaintext

Before merge Sorting --->>

45, 23, 11, 89, 77, 98, 4, 28, 65, 43,

After merge Sorting start--->>

45, 23, 11, 89, 77, 98, 4, 28, 65, 43,

23, 45, 11, 89, 77, 98, 4, 28, 65, 43,

11, 23, 45, 89, 77, 98, 4, 28, 65, 43,

...

4, 11, 23, 28, 43, 45, 65, 77, 89, 98,

 

The binary tree visualization would be shown between each merge step, assuming the BTreePrinter and HeapSort classes are correctly implemented.

Next Steps:

  1. Ensure the BTreePrinter and HeapSort classes are implemented and imported correctly.
  2. Compile and run the code to observe the sorting process and tree visualization.
  3. Modify the array in the main method to test the sorting with different datasets.

Out Put:
Before merge Soring --->>
45, 23, 11, 89, 77, 98, 4, 28, 65, 43,
After merge Soring start--->>
       23              
      / \      
     /   \     
    /     \    
   /       \   
   23       11      
  / \     / \  
 /   \   /   \ 
 89   77   98   4  
/ \ /          
28 65 43          
                               
23, 23, 11, 89, 77, 98, 4, 28, 65, 43,
       23              
      / \      
     /   \     
    /     \    
   /       \   
   45       11      
  / \     / \  
 /   \   /   \ 
 89   77   98   4  
/ \ /          
28 65 43          
                               
23, 45, 11, 89, 77, 98, 4, 28, 65, 43,
       11              
      / \      
     /   \     
    /     \    
   /       \   
   45       11      
  / \     / \  
 /   \   /   \ 
 89   77   98   4  
/ \ /          
28 65 43          
                               
11, 45, 11, 89, 77, 98, 4, 28, 65, 43,
       11              
      / \      
     /   \     
    /     \    
   /       \   
   23       11      
  / \     / \  
 /   \   /   \ 
 89   77   98   4  
/ \ /          
28 65 43          
                               
11, 23, 11, 89, 77, 98, 4, 28, 65, 43,
       11              
      / \      
     /   \     
    /     \    
   /       \   
   23       45      
  / \     / \  
 /   \   /   \ 
 89   77   98   4  
/ \ /          
28 65 43          
                               
11, 23, 45, 89, 77, 98, 4, 28, 65, 43,
       11              
      / \      
     /   \     
    /     \    
   /       \   
   23       45      
  / \     / \  
 /   \   /   \ 
 77   77   98   4  
/ \ /          
28 65 43          
                               
11, 23, 45, 77, 77, 98, 4, 28, 65, 43,
       11              
      / \      
     /   \     
    /     \    
   /       \   
   23       45      
  / \     / \  
 /   \   /   \ 
 77   89   98   4  
/ \ /          
28 65 43          
                               
11, 23, 45, 77, 89, 98, 4, 28, 65, 43,
       11              
      / \      
     /   \     
    /     \    
   /       \   
   23       45      
  / \     / \  
 /   \   /   \ 
 77   89   98   4  
/ \ /          
28 65 43          
                               
11, 23, 45, 77, 89, 98, 4, 28, 65, 43,
       11              
      / \      
     /   \     
    /     \    
   /       \   
   23       45      
  / \     / \  
 /   \   /   \ 
 77   89   98   4  
/ \ /          
28 65 43          
                               
11, 23, 45, 77, 89, 98, 4, 28, 65, 43,
       11              
      / \      
     /   \     
    /     \    
   /       \   
   23       45      
  / \     / \  
 /   \   /   \ 
 77   89   98   4  
/ \ /          
28 65 43          
                               
11, 23, 45, 77, 89, 98, 4, 28, 65, 43,
       11              
      / \      
     /   \     
    /     \    
   /       \   
   23       45      
  / \     / \  
 /   \   /   \ 
 77   89   4   4  
/ \ /          
28 65 43          
                               
11, 23, 45, 77, 89, 4, 4, 28, 65, 43,
       11              
      / \      
     /   \     
    /     \    
   /       \   
   23       45      
  / \     / \  
 /   \   /   \ 
 77   89   4   98  
/ \ /          
28 65 43          
                               
11, 23, 45, 77, 89, 4, 98, 28, 65, 43,
       11              
      / \      
     /   \     
    /     \    
   /       \   
   23       45      
  / \     / \  
 /   \   /   \ 
 77   89   4   98  
/ \ /          
28 65 43          
                               
11, 23, 45, 77, 89, 4, 98, 28, 65, 43,
       11              
      / \      
     /   \     
    /     \    
   /       \   
   23       45      
  / \     / \  
 /   \   /   \ 
 77   89   4   28  
/ \ /          
28 65 43          
                               
11, 23, 45, 77, 89, 4, 28, 28, 65, 43,
       11              
      / \      
     /   \     
    /     \    
   /       \   
   23       45      
  / \     / \  
 /   \   /   \ 
 77   89   4   28  
/ \ /          
98 65 43          
                               
11, 23, 45, 77, 89, 4, 28, 98, 65, 43,
       11              
      / \      
     /   \     
    /     \    
   /       \   
   23       45      
  / \     / \  
 /   \   /   \ 
 77   89   4   28  
/ \ /          
98 43 43          
                               
11, 23, 45, 77, 89, 4, 28, 98, 43, 43,
       11              
      / \      
     /   \     
    /     \    
   /       \   
   23       45      
  / \     / \  
 /   \   /   \ 
 77   89   4   28  
/ \ /          
98 43 65          
                               
11, 23, 45, 77, 89, 4, 28, 98, 43, 65,
       11              
      / \      
     /   \     
    /     \    
   /       \   
   23       45      
  / \     / \  
 /   \   /   \ 
 77   89   4   28  
/ \ /          
98 43 65          
                               
11, 23, 45, 77, 89, 4, 28, 98, 43, 65,
       11              
      / \      
     /   \     
    /     \    
   /       \   
   23       45      
  / \     / \  
 /   \   /   \ 
 77   89   4   28  
/ \ /          
98 43 65          
                               
11, 23, 45, 77, 89, 4, 28, 98, 43, 65,
       11              
      / \      
     /   \     
    /     \    
   /       \   
   23       45      
  / \     / \  
 /   \   /   \ 
 77   89   4   28  
/ \ /          
43 43 65          
                               
11, 23, 45, 77, 89, 4, 28, 43, 43, 65,
       11              
      / \      
     /   \     
    /     \    
   /       \   
   23       45      
  / \     / \  
 /   \   /   \ 
 77   89   4   28  
/ \ /          
43 65 65          
                               
11, 23, 45, 77, 89, 4, 28, 43, 65, 65,
       11              
      / \      
     /   \     
    /     \    
   /       \   
   23       45      
  / \     / \  
 /   \   /   \ 
 77   89   4   28  
/ \ /          
43 65 98          
                               
11, 23, 45, 77, 89, 4, 28, 43, 65, 98,
       4              
      / \      
     /   \     
    /     \    
   /       \   
   23       45      
  / \     / \  
 /   \   /   \ 
 77   89   4   28  
/ \ /          
43 65 98          
                               
4, 23, 45, 77, 89, 4, 28, 43, 65, 98,
       4              
      / \      
     /   \     
    /     \    
   /       \   
   11       45      
  / \     / \  
 /   \   /   \ 
 77   89   4   28  
/ \ /          
43 65 98          
                               
4, 11, 45, 77, 89, 4, 28, 43, 65, 98,
       4              
      / \      
     /   \     
    /     \    
   /       \   
   11       23      
  / \     / \  
 /   \   /   \ 
 77   89   4   28  
/ \ /          
43 65 98          
                               
4, 11, 23, 77, 89, 4, 28, 43, 65, 98,
       4              
      / \      
     /   \     
    /     \    
   /       \   
   11       23      
  / \     / \  
 /   \   /   \ 
 28   89   4   28  
/ \ /          
43 65 98          
                               
4, 11, 23, 28, 89, 4, 28, 43, 65, 98,
       4              
      / \      
     /   \     
    /     \    
   /       \   
   11       23      
  / \     / \  
 /   \   /   \ 
 28   43   4   28  
/ \ /          
43 65 98          
                               
4, 11, 23, 28, 43, 4, 28, 43, 65, 98,
       4              
      / \      
     /   \     
    /     \    
   /       \   
   11       23      
  / \     / \  
 /   \   /   \ 
 28   43   45   28  
/ \ /          
43 65 98          
                               
4, 11, 23, 28, 43, 45, 28, 43, 65, 98,
       4              
      / \      
     /   \     
    /     \    
   /       \   
   11       23      
  / \     / \  
 /   \   /   \ 
 28   43   45   65  
/ \ /          
43 65 98          
                               
4, 11, 23, 28, 43, 45, 65, 43, 65, 98,
       4              
      / \      
     /   \     
    /     \    
   /       \   
   11       23      
  / \     / \  
 /   \   /   \ 
 28   43   45   65  
/ \ /          
77 65 98          
                               
4, 11, 23, 28, 43, 45, 65, 77, 65, 98,
       4              
      / \      
     /   \     
    /     \    
   /       \   
   11       23      
  / \     / \  
 /   \   /   \ 
 28   43   45   65  
/ \ /          
77 89 98          
                               
4, 11, 23, 28, 43, 45, 65, 77, 89, 98,

 

 






Merge sort
Merge sort





 

Merge Sort Visualization

Tags:

Post a Comment

0 Comments

Post a Comment