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

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.     ...
Read more

AVL Tree Rotations

-
Image
Rotations When the tree structure changes, we need to modify the tree to restore the AVL tree property. This can be done using single or double rotations. Types of Violations Let us assume the node that must be rebalanced in X. Violations might occur in four cases: Insertion into the left subtree of the left child of X. Insertion into the right subtree of the right child of X.  Insertion into the right subtree of the left child of X. Insertion into the left subtree of the right child of X. Single Rotation Left Left Rotation (LL Rotation) [Case 1]: Rotation does not have to be done at the root of a tree. In general, we start at the node inserted and travel up the tree, updating the balance information at every node on the path. public AVLTree rotateLeft (AVLTree x) {        AVLTree  y = x.right;        // Perform rotation            y.left = x;    ...
Read more

Disjoint Set (Union-Find)

-
A disjoint-set data structure is a data structure that keeps track of a set of elements partitioned into a number of non-overlapping subsets. Union-Find Algorithm is an algorithm which performs two operations: Find: Determine which subset a particular element is in. Union: Join two subsets into a single subset.   Source code in java import java.util.*; import java.lang.*; import java.io.*; class Graph { int V, E; // V-> no. of vertices & E->no.of edges Edge edge[]; // /collection of all edges class Edge { int src, dest; }; // Creates a graph with V vertices and E edges Graph(int v,int e) { V = v; E = e; edge = new Edge[E]; for (int i=0; i<e; ++i) edge[i] = new Edge(); } // A utility function to find the subset of an element i int find(int parent[], int i) { if (parent[i] == -1) return i; return find(parent, parent[i]); } // A uti...
Read more