I know the complexity of merge sort is (n logn) for all cases but ,what if the cut or partition is imbalance like 4 on one side and 5 on other ,
eg. 9 element array would have a cut at 4 index ,,, so does this imbalance causes the complexity to change from n logn...
like does it changes from n log to any other form like quicksort which best case is n logn but imbalance pivot causes to shift from n logn to n2
Okay so Merge Sort has a time complexity of Θ(n . log n) for all cases. This would include cases where the size 'n' in question is odd.
This is because when you consider time-complexity in Big-Oh notation, you always remove lower order terms that may appear when you finally compute the complexity. If 'n' were to be odd, you would simply have some extra lower order terms factoring in, but they would not affect complexity. For further clarification refer to the following example.
E.g. 'n' is the number of terms, 'c' the constant time for dividing and merging.
On computing the complexity for Merge sort, we get:
cn(log n + 1). (Here 'log n + 1' gives the number of levels in the tree)
However the lower order term '+1' and constant c are discarded when representing in Big-Oh, hence we get Θ(n . log n).
Similarly, in cases where 'n' is odd, you would get some extra lower order terms into this final complexity, but they would not matter as they would get discarded. Complexity does not increase as you doubted. Hope it is clear.
If not please refer to this link to get a better understanding: https://www.khanacademy.org/computing/computer-science/algorithms/merge-sort/a/analysis-of-merge-sort
