Merge Sort is a sorting algorithm used in Computer Science.
Time complexity cases of Merge Sort are:
Best Case Complexity O(nlog n) *
Worst Case Complexity O(nlog n) *
Average Case Complexity O(nlog n) *
So, why the all situations are the same?
Because Merge Sort always works with Divide and Conquer methods.
What are the Divide and Conquer methods?
Divide and Conquer methodologies are coming from the ancient Roman politicians at history. When the ancient politicians decide to develop an efficient method to defeat the enemies, they improved these methods. According to these methods, if you divide your enemies to small pieces, then you can conquer them easily. As a result, hence, we should understand how can we find solutions easily to huge problems.
How Merge Sort algorithm works
1- The first step is dividing unsorted elements into sub element groups. But the dividing have to be at the middle point.
2- If still there are sub element groups to dividing, the second step goes like the before one. The sub element groups need to divide to into sub element groups. If there are not any element groups to dividing,- and all elements are single-, then we must pass to the other step.
3- Let's start pairing with the two single elements which are adjacent. But the pairing should be doing sorted.
4- When all element groups were paired as sorted, then we got a sorted array.
Example 1: [16,21,11,8,12,22]