Merge Sort Algorithm

-
Merge Sort is a Divide and Conquer algorithm. It divides the input array into two halves and then merges the two sorted halves.

Algorithm:

MergeSort(a[], l, r)
If r > l
  1. Find the middle point to divide the array into two halves: middle m = (l+r)/2.
  2. Call mergeSort for the first half: Call mergeSort(a, l, m).
  3. Call mergeSort for the second half: Call mergeSort(a, m+1, r).
  4. Merge the two halves sorted in step 2 and 3: Call merge(a, l, m, r).
The following diagram:

Source code in Java:

class MergeSort
{
     // Merge two subarray of a[].
     // First subarray is a[l...m].
    //  Second subarray is a[m+1....r].  

   void merge(int a[], int l, int m, int r)
   {
        int n1 = m-l+1;
        int n2 = r-m;

       // Create temp array.

       int L[] = new int[n1];
       int R[] = new int[n2];

      // Copy data

      for(int i=0;i<n1;i++)
             L[i] = a[l+i];
      for(int j=0;j<n2;j++)
             R[j] = a[m+1+j];

      int i= 0, j= 0;
      int k = l;
      while(i < n1 && j < n2)
      {
           if(L[i] <= R[j])
           {
                 a[k] = L[i];
                 i++;
           }
           else
           {
                a[k] = R[j];
                j++;
           }
           k++;
      }

      // Copy remaining list of L[] if any
      while(i < n1)
      {
               a[k] = L[i];
           i++;
           k++;
      }
      
      // Copy remaining list of R[] if any
      while(i < n2)
      {
               a[k] = R[j];
           j++;
           k++;
      }
   }

// Sort array 

   void sort(int a[], int l, int r)
  {
         if(l < r)
        {
             int m = (l+r)/2;

             sort(a, l, m);
             sort(a, m+1, r);

             // Merge the sorted halves
             merge(a, l, m, r);
         }
   }

   static void printArray(int a[])
   {
          int n = a.length;
          for(int i=0;i<n;i++)
               System.out.print(a[i]+" ");
          System.out.println();
    }

    public static void main(String arg[])
    {
               int a[] = {29,10,14,37,13};
           
          System.out.println("Given Array);
          printArray(a);

          MergeSort obj = new MergeSort();
              obj.sort(a,0,a.length-1);

          System.out.println("\nSorted array");
          printArray(a);
     }
}


Output:

Given array is
29 10 14 37 13

Sorted  array is
10 13 14 29 37           
      

Comments

Post a Comment

Popular posts from this blog

Tree

-
Image
What is Tree? A tree is a data structure, each node points to a number of nodes. A tree is an example of non-linear data structures. A tree structure is a way of representing the hierarchical nature of a structure in a graphical form. The root of a tree is the node with no parents. A node with no children is called a leaf node . Children of the same parent are called siblings . A node "p" is an ancestor of node "q" if there exists a path from "root" to "q" and "p" appears on the path. The node "q" is called descendant of p. Set of all node at a given depth is called the level of the tree. The root node is at level zero. The height of the tree is the maximum height among all the nodes in the tree and depth of the tree is the maximum depth among all the nodes in the tree. Binary Tree A tree is called a binary tree if each node has zero child, one child or two children. Types of binary tree Stric
Read more

AVL (Adelson-Velskii and Landis) Trees

-
Image
What is AVL Tress? A binary tree is said to be an AVL Tree if: It is a binary search tree. For any node, the height of left subtree of node and height of right subtree of node differ by at most 1. Minimum/Maximum number of Nodes in AVL Tree Let the height of an AVL Tree is h and N(h) indicate the number of nodes in AVL Tree. Minimum number of nodes with height h is: N(h) = N(h-1) + N(h-2) + 1 N(h-1) indicates the minimum number of nodes with height h-1 . N(h-2) indicates the minimum number of nodes with height h-2 .   AVL Tree Declaration The declaration of AVL is similar to that of BST (Binary Search Tree). We include the height sldo as a part of a declaration. public class AVLTree {          int key, height;           AVLTree  left, right;           AVLTree  (int data) {                 key = d;                 height = 1;          }                 public int findHight( AVLTree  root ) {                 if(root
Read more

How to Build REST API Using PHP

-
Image
Create REST API in PHP API stands for Application Programming Interface and the idea behind API is to connect different applications irrespective of their platforms to share information. Generally, API takes requests from different applications, processes it and gives back the response. What is REST API? REST stands for Representational State Transfer and it means that the request and the response should contain a representation of the information i.e., should be in a certain format. So basically, the requests must use proper HTTP methods and the response must be in a proper format like JSON or XML instead of plain text. REST API is nothing but a normal API with a set of principles. We need to follow a set of rules while creating and consuming REST API. The rules include the following : 1. Use appropriate HTTP methods while performing API calls. The following are the four primary HTTP methods which should be used to send and receive API requests.       a. GET   
Read more