MergeSort is one of the most popular sorting algorithms. In this article you will learn about the features of MergeSort and how to implement the sorting algorithm in Dart. Of course, this code will also be explained.
If you want to follow me further in this series and are interested in other articles, then I recommend you to follow me.
Enjoy the read!
Introduction
To explain MergeSort in a basic way, we will use a card example. We imagine a deck of cards, where the cards have numbers from 1–10. We now want to sort the shuffled deck of cards.
To begin with, we divide the deck in half. Then we divide this half again. We do this until each card stands alone.
Now we compare two adjacent cards. If the right one is bigger, it goes to the beginning and vice versa. Then we compare two adjacent piles again and so on.
Properties
First we look at the time complexity of MergeSort. We have given an array with n=8 elements. So 3 levels of divisions are needed. We denote these as d.
Source: https://www.javatpoint.com/daa-merge-sort
So in this example, d is the logarithm of 8 to the base 2, so d=log₂8, since in general d=log₂n. This is the complexity class when dividing. Thus, we obtain O(log n).
When merging, each element stands alone, making n/8 for one element in our example. Now two elements are merged, therefore we get 2x(n/8) = n/4. Each element is iterated through once during the merging, which gives us a time complexity of O(n). Merging both time complexities gives O(n log n).
Source: https://www.javatpoint.com/daa-merge-sort
Note: This was an extremely simplified version to explain the time complexity. The correct mathematical explanation is much more complicated. It is possible that this derivation is wrong!
You can find a more detailed version here: https://iq.opengenus.org/time-complexity-of-merge-sort/
Two elements to be compared are only swapped if the right one is smaller than the left one, but not if they are of the same size. Thus MergeSort is a stable algorithm.
MergeSort is one of the few algorithms that cannot be executed in-place. This is due to the divisions of the arrays that are performed.
Implementation in Dart
We now want to implement the sort algorithm in Dart. To do this, the input array must be divided into sub-arrays. These must be divided again until each element stands alone. Then two sub-arrays are compared with each other. This is then also done for the other sub-arrays. To compare two sub-arrays, a merge-index is set to the first position of both lists. Now these two merge-indexes are compared. The merge-index, which has the smaller value, changes the position in the array by one place. Now the two indices are compared again. After a merge-index has arrived at the last element of the one sub-array and this element is then put into the result list, this is completely sorted. But the other sub-array is not yet completely sorted in. Therefore, the last elements of the remaining sub-array are inserted at the end into the result list.
Here is a possible implementation in Dart:
If you want to copy out the code, you can find it here.
Conclusion
In this post we have looked at how MergeSort works and how you can implement the sorting algorithm in Dart.
I hope you were able to learn something and enjoyed it! If so, I’d be very happy if you give this post some claps.
Oh, and before I forget to mention it: I’ll be introducing some more sorting algorithms in Dart in the near future. If you don’t want to miss that, you should definitely follow me!
Have a nice day!