O of N Log N method
Now that we have taken a look at 4 of the Big O notations here, let’s take some time looking over O(n log n). This is also known as a merge sort. What happens in this is we halve the arrays and stitch them back together in order:
Now that we can see the steps in how the merge sort is done, let’s go about trying to figure out how to code this method. To start, we will use the same set of numbers that was used in the previous example and first start off by getting all of our numbers into their individual values:
What we are doing here is creating a left and a right list. These lists will then continue to sort themselves out until just 1 value remains in each list. Once finished, we can see if we get each individual value to show up in our console:
As we can see, the individual values are now showing up. Next, we need to code in a method to let us sort these values into numerical order:
What we have done here is told unity that depending on what number is small, we want to add it to the end of our list and repeat until we have completed our sort. In order for us to view the process in the console, we will run a foreach loop at the beginning of our new while loop to tell us where in the process our loop is at:
As we can see from the start of the console, the list is starting to be sorted out. It is moving our values to the next numerical order and moving onto the next number:
At the end of our console, we can see that our list has been sorted numerically, aside from the last number as our loop doesn’t go back to the beginning once the last number is properly placed:
In our inspector, we can see the change from the unsorted to the sorted list.
Now let’s take a quick look at how much of a difference we have between the O(n log n) and O(n²). To do this, we are going to create a random list of 1000 items and count how many processes it takes for it to sort each of the lists:
With this set up in both of our sorts, we just add in some counts in each of the loops for the processes and let’s see how it differs between the 2:
As we can see, with just a list of 1000 items, we have our bubble search taking 500k counts while the merge sort method is just shy of 23k counts.
There we have it. We have built a O(n log n) to sort through our list. This method takes a bit of code to build, but as a competitor to the O(n²), it is a method that is generally better when working with thousands of different values that need to be sorted through. Otherwise, we are generally better off working with a O(n²) method.