Skip to main content

Merge-Sort

Merge Sorting

 Merge sorting also works on the principle of "divide and conquer".The algorithm of merge sort is quite different from that of quick-sort but its best case performance is also O(nlog(n)).The step by step process is-

  1. Divide the unsorted list into n sublists, each containing 1 element (a list of 1 element is considered sorted).
  2. Repeatedly merge sublists to produce new sorted sublists until there is only 1 sublist remaining. This will be the sorted list.
How it is actually implemented is described here....
  1. Firstly divide the given array of n elements into n individual numbers.
  2. Then compare the adjacent elements and merge them in the sorted order.
  3. Then compare the corresponding elements of the resulting lists and arrange them in the sorted order.
  4. And finally the sorted list will be obtained.
The following link will help you in understanding it.

Want to see the example code..??
CLICK HERE

Complexity Analysis of Merge Sort

Worst Case Time Complexity : O(n log n)
Best Case Time Complexity : O(n log n)
Average Time Complexity : O(n log n)
Space Complexity : O(n)
  • Time complexity of Merge Sort is O(n Log n) in all 3 cases (worst, average and best) as merge sort always divides the array in two halves and take linear time to merge two halves.
  • It requires equal amount of additional space as the unsorted list. Hence its not at all recommended for searching large unsorted lists.
  • It is the best Sorting technique for sorting Linked Lists.
Labels:

Comments

Post a Comment

Comment on articles for more info.

Popular posts from this blog

Cordova viewport problem solved

Include the viewport settings in Cordova If you are facing the auto zooming problem of cordova then go read on the full article. Cordova actually ignores the viewport meta tag which causes the pixel density problem. So we need to tell cordova that viewport tag is equally important as other tags. To do this, we need to add some code to a file which is specify in the article. Corodva messes with pixels If you are using the latest cordova version or creating the cordova app for latest android versions then you may have faced the zoom malfunctioning.I also faced it when creating an app. Many of you may have already searched the web and found the answer of changing the meta tag attributes to get it working. But adding target-densitydpi=medium-dpi does not solve the problem for latest android versions. It may work for gingerbread but not for kitkat and others. So the final solution which i found was one of the stackexchange answer but rarely found. So i am gonna two things here, i ...
5 comments
Read more

Image Search Engine Using Python

Images provide a lot more information than audio or text. Image processing is the prime field of research for robotics as well as search engines. In this article we will explore the concept of finding similarity between digital images using python. Then we will use our program to find top 10 search results inside a dataset of images for a given picture. It won't be as good as google's search engine because of the technique we will be using to find similarity between images. But what we are going to make will be pretty cool. So lets start. Setting up the Environment Our Algorithm How the code looks Lets build the GUI Additional Techniques Setting up the Environment The code we are going to write requires a few tools which we need to install first. I will try to be as precise as i can and if you get stuck into installing some tool then you can drop a comment below and i will help you sort out the problem. So here are the tools and the steps to install ...
18 comments
Read more

Authentication System : Basic Design

Being a system administrator, it is our main concern to protect users' data from theft and corruption. Regarding theft, we focus in building a sophisticated but secure authentication system which can fulfill all the basic needs we discussed in the last article . In the previous 2 articles, we learned about authentication and authorization. Also we understood the complications in building a secure system which can prevent tresspassing. But we have not code anything yet to build something. So in this article we will be designing an authentication system which will provide the functionalities we want and which will help us understand how the tech giants like google have taken security to another level. We will be writing code in php but the same applies to other languages also. What we'll be using Blueprint Building the system Running the system Additional Care What we'll be using Lets see what are the languages we will be using and database plus som...
Post a Comment
Read more