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

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

One of the best Torrent caching service.

Hi readers, It's been a long time since I made my last post on this blog. That's due to the migration of the blog to private servers.  Today I found a decent torrent caching service, which I have been looking for years. Initially, when I started, I couldn't find the services are really benefiting me. So I went with my own Virtual Private Server in Digital Ocean. I ran a five dollar per month instance for my torrent caching as well as a multipurpose server.  Of course, It has its pros and cons.  Pros: I was able to do anything I wanted. It served as a good multipurpose server. Relatively inexpensive. Cons: You need to be a computer geek for up and running. Even most of the things are automated, still few manual works have to be performed. It takes usual time for downloading unlike caching services(They can do it instantly). Finally, we have a hassle free torrent caching service  Seedr .  It is a free torrent caching servic...
Post a Comment
Read more