Merge sort is a wonderful, widely used sorting algorithm, with consistent data-independent performance. When not in-place merge sorting, that is when the source and destination array are not the same, performance is O(nlgn). When in-place, so the source and destination array are the same, performance is slightly slower: O(nlg2n). Because not-in-place sorting algorithms are faster, implementations frequently allocate memory for the destination array, copy the sorted result back into the source array, and proceed to deallocate the destination array. STL uses this type of a strategy to construct a fast in-place sort from a faster not-in-place sort whenever memory is available. Of course, when memory is not available, in-place sort is necessary, and STL also provides such an implementation.