In sorting n objects, merge sort has an average and worst-case performance of
O(n log n)
.
Merge Sort's most common implementation does not sort in place. In those cases the space complexity is
O(n)
.
It is a stable sorting algorithm which means that the order of equal elements is the same in the input and output.
Wikipedia