 Merge sort's most common implementation does not sort in place; therefore, the memory size of the input must be allocated for the sorted output to be stored in (see below for versions that need only "n"/2 extra spaces).Variants of merge sort are primarily concerned with reducing the space complexity and the cost of copying.A simple alternative for reducing the space overhead to "n"/2 is to maintain "left" and "right" as a combined structure, copy only the "left" part of "m" into temporary space, and to direct the "merge" routine to place the merged output into "m".