Merge sort is used when we want a guaranteed running time of O ( n log ⁡ n ) O(n \log n)       O(n log n), regardless of the state of the input. Merge sort is a stable sort with a space complexity of O ( n ) O(n) O(n).