A Merge Sort is a sorting algorithm that works by dividing an unsorted list into sublists that all contain 1 element, and then by repeatedly merging these sublists until there is only 1 sorted list remaining. Merging sorted sublists(single element sublists are always sorted) is very efficient because it only requires one comparison between the current elements of either sublist to add an element to the merged list.
[Example] [Example]
[Resource] [Resource]
| Performance | ||
|---|---|---|
| Worst case performance | O(n log n) | |
| Best case performance | Ω(n log n) | |
| Average case performance | Θ(n log n) |
Step by Step
The Java Cheat Sheet 