Skip to main content

Merge Sort Implementation in C++

For a Programmer sorting is an easy task after writing the code for couple of pages. But there are many other sorting algorithms. 

The question which is not being properly answered is which sorting algorithm you should choose. 

This is the most frustrating situation where we feel bad about us. The best sorting algorithm depends only on the scenario in which you are intended to use. 



Let us speak about the Merge sort.

  1. Merge sort uses the divide and conquer approach.
  2. Entirely the merge sort is an easy algorithm (Depends on the way you think).
  3. You cannot master merge sort until you think what is happening.
  4. It has a good worst case performance (0(N logN)).
  5. It uses an additional space to accomplish the goal.
  6. The implementation is mainly based on the recursion.
  7.  You can get real performance benefit when comparing to bubble,selection sort.


That's enough for the quick intro. If you would like you know more do a research on yourself.


The algorithm goes like this:

  • Take the array and divide it until you get single element.
  • Each array will yield two sub-arrays. Each sub-array will give two and goes on..
  • Now at the end you will get only single elements.
  • All the single elements are again combined in the same way while ensuring the elements are in the proper order.
  • Finally you will get the sorted array as a present. 


Don't panic looking at the algorithm, i will ensure good amount of comments n my code.


Just look at the image to get good view of what is happening.
Magic of merge


Just looking at the image is not sufficient. Get your hands dirty by working with pen and paper.
Don't get surprised about the failure. Do it again and again until you get success.



The code goes here...





Try to code on your own instead of doing a copy paste. Also remember the mantra for success.

CREDIT: HackerEarth.com(Code monk) for the stuff and the image.
Labels:

Comments

Post a Comment

Popular posts from this blog

Blogger.com VS Wordpress.com

Important : Here we compared Wordpress.com and not Wordpress.org Introduction:      First speaking of blogger. It was developed in Pyra labs then later acquired by Internet giant Google. This is completely free blogging platform written in Python. It integrates with most of google services. I am using blogger for the past two years. It is very compact and comfortable.      After speaking about Wordpress. It is developed by Automattic,Inc powered by opensource CMS(Content Management System) Wordpress written in php. It has very fine features such as landing page, sliders, etc. This is also a free platform but you have an option to get premium service too. I think this intro is good enough. Now let compare their features. Blogger Features: Just one google account is good enough to do anything. Integrates into your Gdrive, Photos,Google+. E-mail feeds are very easy to setup with Google owned Feed Burner service. Simplified user interface. ...
4 comments
Read more

2-Dimensional Array with Dynamic Rows and Columns.

In Programming many times we have to store and work  with the data. But choosing the right way of storing is important. Array is one of the most simple and effective way of storing list of data.Now we have to multiple array of data. Ohh! that sounds easy we can use 2 Dimensional Array. I agree 2 Dimensional array is suitable but I have arrays of variable lengths. So simply creating 2-D Array will not be efficient because I have to specify the column size as the highest of my arrays. So there will be lot of unused space. The good solution can be Dynamic 2D Array with variable columns. Also Array of vectors can also be used. But we are not discussing about STL. Algorithm: Create a ptr to ptr to ptr with the name of your 2D Array to hold the Array of Pointers. Now create an Array of pointers depending on the no of rows and store the base address on the ptr to ptr. For every Row allocate the required memory and store the address in the array of pointers. You own the 2D...
Post a Comment
Read more

Pen drive Shortcut Problem

This guide is to recover your pen drive from shortcut into files.       Sometimes when you plug in your pendrive the contents inside your pendrive apperars to be shortcut. This is caused due a virus which cannot be fixed by your antivirus programs.  Be cool it is easy to fix and your files are safe.   Important don't delete those shortcut items.   1.Just find the drive letter assigned to your pen drive.(shown in windows explorer,eg: e: or f: etc)    2.Now open command prompt.(start->run->type cmd)    3.Type  attirib -h -r -s /s /d x:\*.*      Where  x  denotes your drive letter. Replace  x  with appropriate drive letter.    4.Press enter.  Now your shortcuts will be turned into files.  For any queries please comment below.
Post a Comment
Read more