It halves the array once and then does linear work

There are about lg n levels of recursion and merging does about n work per level, giving about n lg n

It makes n recursive calls, each doing constant work

Each merge is quadratic, but there are only lg n merges