Fast Sorting Algorithms Part 1
In lesson 3 of Unplugged Algorithms, there are two fast sort algorithms explained which are Merge sort and Quick sort today I will explain only merge sort so I will divide this lesson into two lessons and when I do so it will be an easier task for me and you as a reader also😅.
Merge sort depends on splitting the big problem into smaller problems. so it will be an easier problem to solve because splitting the big problem weakens its complexity.
Imagine that you have an array of 16 elements and want to sort them if you deal with the 16 elements at once it will be more difficult but what if I divide it into 2 arrays and sort each array alone the difficulty decreases by half as I will only deal with 8 elements.
And what if I divided each array of 8 elements into two arrays each one having 4 elements the difficulty will keep decreasing as shown in the image below. If we keep dividing the array we end up with an array of 1 element and the problem converted from sorting 16 elements to sorting 2 elements only.
After sorting the 2 elements only we will climb the tree recursively with an array sorted in ascending order and then when comparing the two arrays that have bigger lengths but now it will be easier because we have already granted that both arrays we compared are sorted.
As the final step, we will have two big arrays containing the elements of the original array and each of them is sorted that will make our mission easier as if the first element in the left array is smaller than the first element in the right array then it is the smallest one in both of them and we guarantee that we put it in the right spot.
To make our code cleaner and less complex we will make a standalone function that is responsible for merging two sorted arrays into one array and call it mergeArrays:
Explain how does mergeArrays function works with an example in the below image:
Then we will start implementing a mergeSort function that will make use of:
- Itself in dividing the original array into smaller arrays (recursion).
- the mergeArrays function to sort the divided arrays.
Explain how does mergeSort function works with an example in the below image:
Is this algorithm more efficient than the insertion sorting algorithm?
yes, it’s much more efficient In half a second (500 ms) of computation time, Sorting by insertion can sort sequences of length up to 8,000, whereas Mergesort manages 20 times as many numbers simultaneously.
Why it’s more efficient?
because as we mentioned before the insertion sort algorithm time complexity is O(n²) but the time complexity for merge sort is O(n log₂(n)) and that’s because if we have an array of 16 elements it will be decomposed in 4 levels (log₂(16) = 4) and If we calculate the total of comparisons in each decomposition we will find it equal to n so we get O(n log₂(n)).
That’s it for today stay tuned for the second part of this lesson where we will talk about a quick sort algorithm that is quicker than merge sort🤯.
