The "Polite" Merge Sort
Another old-classic problem: the Merge Sort. Merge Sort Algorithm The problem of the classical implementation The whole algorithm is explained in the wikipedia link above, so I’ll focus on the problem here. The Merge Sort is an in-place-sorting-algorithm that requires some support memory to do it’s calculations. At the “merge step”, an amount of memory as large as the current portion of array being merged is allocated to be used as priority queue (again, the why is easy to find on the web). After this memory is used, normally get’s released. ...