How to analyse the worst-case time complexity of this algorithm(a mix of Bubble Sort and Merge Sort)?
Let $f(n)$ the maximum number of elementary operations performed by the algorithm when the number of elements to sort is $n$.
An upper bound to the worst-case complexity of the algorithm is $O(n^2)$ since there exists some $n_0$ and some constant $c&gt;0$ such that for every $n \ge n_0$, $f(n) \le c n^2$.
Moreover, given some other function $g(n) = o(n^2)$ it is false that $f(n) \in O(g(n))$ since for all $c&gt;0$, there always exists a sufficiently large $n$ for which $f(n) \ge c g(n)$.  In this sense, $O(n^2)$ is the smallest asymptotic upper bound you can hope to obtain.
Notice however that with this choice of $f(n)$ it is not true that $f(n) = \Omega(n^2)$ according to Knuth's definition of big Omega, while it is true in the Hardy–Littlewood definition.
The &quot;problem&quot; here is that $f(n)$ is not monotonically non-decreasing, while the functions considered in algorithm analysis usually are.
Of course you can define $F(n) = \max_{0 \le n' \le n} f(n')$ to get a monotonically non-decreasing function, which is probably what you have in mind when you think of the worst-case running time of the algorithm.
Then you have:
$F(n) = O(n^2)$ and $F(n)= \Omega(n^2)$ showing that $F(n) = \Theta(n^2)$.