Merge sort algorithm (Java)
By Peter
Merge sort algorithm details:
Worst-case Time Complexity: O(n log(n))
Space Complexity: O()
The algorithm
Merge sort is comparison based algorithm, from the efficient sorting category. The algorithm is based on “Divide and conquer” (John Van Neumann), which means in this case, that the original collection is divided into smaller chunks. This idea can be implemented in a recursive fashion, so that the collection is divided into single elements and then re-constructed into a sorted collection. The re-construction, merging part of the algorithm is the step where the elements are ordered. In each merge stage the elements are put into the they sorted positions, in the sub collection. Breaking the original collection into it’s elements can create additional iterations(computation), and is not required. Handling the sub collections can be in place so it does not require separate collection(s).
The performance of the Merge sort algorithm is O(n log(n)) which is very impressive. I would suggest to use a default library, in a real world application as most of the languages nowadays are implementing a better performing algorithm as default sorting option. In Java the Util package contains a sort method, in the Arrays class. Based on the documentation the implementation is Dual-Pivot Quicksort which performs O(n log(n)) time complexity.
As an example, an 8 element integer collection would be sorted as follows:
Java implementation
My implementation of the merge sort algorithm in java:
The above code snippet is using the Comparable interface, to simplify the code. It allows to define the sorting order as ascending or descending. In the code I am using a helper array to simplify the code, to copy elements back into original array. This is not necessary with an in place merge sort, an example of this can be found here.
The complete implementation with unit tests is available in my Java Algorithms Github Repo, https://github.com/pete314/algorithms-java