This content originally appeared on Level Up Coding - Medium and was authored by Mohamed Hijazi
Previously, we saw the least performant algorithm in the Big O notation family: Bubble Sort (Big O Notation: Bubble Search in Unity). In this article, we will dive in a much more efficient type of sort and a new Big O notation which is the Merge Sort.
Understanding Merge Sort
Merge sort algorithm is basically dividing a big data array into individual array (ONE INDEX PER ARRAY), so each array will hold one value. From there, the merge will start sorting and merging each individual array until it merges all the data into a one sorted array.
In terms of Big O notation, the merge sort is referred to as: O(n log n), which is dividing and conquering so it is a mix of a linear search O (n) and a binary search O (log n).
Implementation
Let’s take the following int list as an example:
List<int> ages = new List<int>{43, 76, 2, 2, 5, 45, 25};The process will be divided into two methods, one method that will divide the array into individual lists of one index per array, and the second method will start sorting and merging.
Dividing Part
Just like in binary search (Big O: Binary Search in Unity), we will divide the list into a left list and a right list. Then we will take the new lists, and divide them into their new left and right lists, and we keep dividing until there is only one index in the list. Sounds simple enough? Let’s implement it…
As you can see, this method will take a list, and start dividing it into left and right lists and keep doing so until it reaches individual lists. In the end of this method, we created a new method called MergeLists that takes two lists as parameters.
Merge Part
What this method is doing is that it takes the two left and right lists, checks if they are not empty, and then adds compares the lists and adds them to a sorted list.
Bubble Sort Vs Merge Sort
Now that we know how to do both sorts, let’s quickly test the difference in efficiency for both algorithms.
Say we have a list of 1000 items, and we check how many times each algorithm is run in order to sort the list. We do this by adding a count in each iteration.
As you can see, the bubble sort took 500,500 iterations in order to sort a list of 1000 numbers, while the merge sort only to 22,950 iterations in order to sort the same list.
Big O Notation: Merge Sort in Unity was originally published in Level Up Coding on Medium, where people are continuing the conversation by highlighting and responding to this story.
This content originally appeared on Level Up Coding - Medium and was authored by Mohamed Hijazi
Mohamed Hijazi | Sciencx (2021-08-29T23:17:52+00:00) Big O Notation: Merge Sort in Unity. Retrieved from https://www.scien.cx/2021/08/29/big-o-notation-merge-sort-in-unity/
Please log in to upload a file.
There are no updates yet.
Click the Upload button above to add an update.