Merge Sorting !

Hello All ,  

In this section i am going to discuss one of the famous sorting technique available for us . 

Merge sort : 
The main idea behind this sorting is , we first need to divide the set of elements to half , sort on both sides and merge them . This way we are eliminating the need for traversing entire elements .

This technique is a stable sort .

What is a stable sorting ? - In stable sort the implementation or algorithm tries to preserve the order of equal elements , meaning if two objects with equal keys appear in the same order as in the input. I have found this very good example from wiki pages which might clear the things for us .

In this beautiful example , we have two 5s after different type . A stable sort tries to preserve the order in the output .

Now let us come back to merge sort . As mentioned above it divides the elements ,sort & merge as explained in the below figure .

My advise for all the readers is , try to come up with your own logic before looking at the code below . Come back and check my implementations 

Coming to finding the complexity of this algorithm , as we have seen in one of the article "Finding complexity " we will  use our knowledge to find the complexity here  .

As we have seen in the above approach ,  we would be dividing the set of elements into half for each iteration which gives us the complexity as logn .

Now , for each of the set we sort the elements . So in total there will be n elements that needs to be checked and sorted ( combining all the sets)

So the final complexity of this sorting method would be O(nlogn)

#include

#include

char temp[10]={4,2,10,6,7,9,22,1,8};

void merge_sort(int low, int mid, int high)

{

  char local[10];

  int i,k ;

  int a,b;

  a = low;

  b = mid+1;

  i=low;

  while((a <=mid) && (b<=high))

  {

    if(temp[a]<=temp[b])

    {

      local[i]=temp[a];

      a++;

    }

    else

    {

      local[i]=temp[b];

      b++;

    }

    i++;

  }

/*For the left over elements during the swap operation ..

 * this will be calculated from the position of left & right partitioned values

 * */

  if(a>mid)

   {

     for(k=b;k<=high;k++)

      {

        local[i]=temp[k];

        i++;

      }

   }

  else

  {

     for(k=a;k<=mid;k++)

      {

        local[i]=temp[k];

        i++;

      }

  }

  for(k=low;k<=high;k++)

   temp[k] = local[k];

}

void parition(int low , int high)

{

  int mid ;

 if(low

  {

    mid = (low+high)/2;

    parition(low,mid);

    parition(mid+1,high);

    merge_sort(low,mid,high);

  }

}

void main()

{

   int i =0;

   parition(0,8);

   printf("After sorting the array\n");

  for(i=0;i<9 i="" p="">

   printf("%d ",temp[i]);

}

Hope i am able to come up with an efficient solution !