Merge Sort: What is Merge sort and Its complexity
Hi, this is Shubham Mishra, today we will be going to discuss on a topic which deals with the sorting of an array. In my algorithm series, this is the first post but previously I also have written other posts such as Python game develop using Pygames and Data structure and data structure types.
The today's topic is Merge sort algorithm. In the series of the algorithm, we will discuss all the possible kind of algorithms and also its complexity with the condition for the use of such algorithms. Let's discuss Merge sort algorithm, its time complexity. Merge sort is a very efficient sorting algorithm with the near-optimal number of comparisons. It is best described using a Recursive algorithm approach. The working of merge sorting algorithm is to splitting and merging of two sorted lists into one sorted list. The recursive algorithm used for merge sort comes under the category of divide and conquer technique. An array of n elements is split around its centre which leads to two small arrays. In this way, the two sub-arrays are further divided into half until a condition match and then all the small subarrays are sort independently and merged to produce the sorted array. Bored, don't worry we have below diagrammatic representation for the above text.
In the above diagram, we do have an Initial array as [ 34, 5, 9, 14, 64, 8] and we get our sorted array at the last step. It is self-explanatory that how things are working in the above diagram. Now let's jump into the coding.
Done with the code part.
The today's topic is Merge sort algorithm. In the series of the algorithm, we will discuss all the possible kind of algorithms and also its complexity with the condition for the use of such algorithms. Let's discuss Merge sort algorithm, its time complexity. Merge sort is a very efficient sorting algorithm with the near-optimal number of comparisons. It is best described using a Recursive algorithm approach. The working of merge sorting algorithm is to splitting and merging of two sorted lists into one sorted list. The recursive algorithm used for merge sort comes under the category of divide and conquer technique. An array of n elements is split around its centre which leads to two small arrays. In this way, the two sub-arrays are further divided into half until a condition match and then all the small subarrays are sort independently and merged to produce the sorted array. Bored, don't worry we have below diagrammatic representation for the above text.
 |
| Merge Sort Algorithm |
In the above diagram, we do have an Initial array as [ 34, 5, 9, 14, 64, 8] and we get our sorted array at the last step. It is self-explanatory that how things are working in the above diagram. Now let's jump into the coding.
Done with the code part.
Now let's discuss the complexity of merge sort algorithm. The merge sort algorithm's main computation power required for 'merge_with_sorting_function' this function, when the subarrays are merged and get sorted. Its time complexity is O(N log N), where N is the total number of elements in the array.
While considering its complexity one important thing need to consider is the memory required by this algorithm, but that is a one more arrays as in our case it was 'temp[]' which is not harmful so I would like to conclude that Merge Sort algorithm is an Efficient algorithm.
Thanks for scrolling down, In my upcoming posts I would like to discuss more and more algorithms and will also differentiate them from others.
Thank You !!!
See my all posts Shubham Mishra
Visit Radix Sort algorithm
See my all posts Shubham Mishra
Visit Radix Sort algorithm
Ok great, we are done with this post,
Now if you like my way of talk, lets explore more blogs written by me and my inner knowledge,
Get to know answers for common search on Google : A blog for posts which can help you for daily life problems, such as where to get free images, Topic suggestion for the blog.
Computer Science algorithms and other knowledge share : A blog for posts such as best search algorithm, Top interview questions for diffrent technologies, knowledge share for some frameworks or programming languages for the interview or in general terms.
My ideas to solve real world problems : A blog where me shared and presented my ideas to solve a real world problems, this will be interesting for me.
Future of computer science technology discussed : A blog where me discussed about the future of computer science and new technologies which will change our way for looking to solve problems.
Ruby on Rails Web development Blog : As the name suggest, it is the blog for sharing few knowledge about RoR web development framework.
Liked my blogs, wanna to connect:
Thanks for reading this post, Have a good day :)
Comments
Post a Comment