Merge sort is based on divide and conquer technique in which the list breaking down into several sub-lists until each sublist consists of a single element and merging those sublists in a manner that results into a sorted list.
- At first, divide the unsorted array into two half-sized sub-arrays.
- Continue to divide the sub-arrays until the array has one element.
- Merge each sub-array pairs together by keeping the lowest value first.
- Repeat step3 until there are no sub-arrays left.
| Best | Average | Worst | Space (Memory) | Stable | Advantage |
|---|---|---|---|---|---|
| Ω(n log(n)) | θ(n log(n)) | O(n log(n)) | O(n) | Yes | Sort efficiently large data sets |