Table Of Contents
* π€ INTRODUCTION
* ππ» ABOUT MERGE SORT ALGORITHM
* π¨π»βπ« EXPLANATION
* π VISUAL EXAMPLE
* π IMPLEMENTATION
* π©π»βπ» CODE
* π€ COMPLEXITY
* π THANK YOU
π€ INTRODUCTION
Welcome, hackers! I hope you are all having a great weekend.πBefore we start another work week tomorrow, let's learn something new. In this blog article, we are going to explain and implement the Merge Sort algorithm.
ππ» ABOUT MERGE SORT ALGORITHM
Merge sort algorithm is another divide-and-conquer algorithm based on the idea of breaking down a list into several sub-lists until each sublist consists of a single element and merging those sublists in a manner that results in a sorted list.
Let's take a generic array that starts at index p and going through index r. It will be convenient to have a notation for a subarray, array[p..r]; In terms of our notation, for an array of n elements, we can say that the original problem is to sort an array A[0..n-1];
π¨π»βπ« EXPLANATION
Here is how merge sort uses divide-and-conquer:
Divide - by finding the number q of the position midway between p and r. Do this step the same way we found the midpoint in binary search: add p and r, divide by 2, and round down.
Conquer - by recursively sorting the subarray in each of the two subproblems created by the divide step. That is, recursively sort the subarray array[p..q] and recursively sort the subarray array[q+1..r];
Combine - by merging the two sorted subarrays back into the single sorted subarray array[p..r];
π VISUAL EXAMPLE
Steps:
0: Array [14, 7, 3, 12, 9, 11, 6, 2] is unsorted
1: Find q (q = (p+r)/2) q=3 in our case
2: We divide into two subarrays [14, 7, 3, 12] - up to the index of q - And [9, 11, 6, 2]
3: Find q again in this case for each of the subarray
The first subarray q index is 1 and for the second q=5
4: We divide into the following subarrays:
[14, 7] and [3, 12] for the first subarray and [9, 11] and
[6,2] for the second subarray.
...Repeating these steps until we have only single values as an array member. We have to make two recursive calls in the conquer step.
π IMPLEMENTATION
π¨π»βπ» CODE
Play with the code!
π€ COMPLEXITY
The complexity of the Merge sort algorithm is in the very best case Big O of nlog2n, in the worst case, the merge sort is staying consistent with the complexity of Big O of nlog2n.
The bad thing about the Merge sort algorithm is that requires an extra memory space the same size as the vector that is being sorted.
π THANK YOU FOR READING!
References:
School notes...
School books...
Khan Academy
Please leave a comment, tell me about you, about your work, comment your thoughts, connect with me!
β SUPPORT ME AND KEEP ME FOCUSED!
Have a nice time hacking! π
Top comments (1)
Try to check your version of the algorithm on the array of 1 000 000 items at least. You would be surprised