phishman3579/java-algorithms-implementation

In-place merge sort

timiscoding opened this issue · 1 comments

timiscoding commented

Regarding MergeSort.java

In the source code comments, it states "Space: In-place." and according to "In-place algorithms" wikipedia states

"an in-place algorithm (or in Latin in situ) is an algorithm which transforms input using a data structure with a small, constant amount of extra storage space. The input is usually overwritten by the output as the algorithm executes."

However, in line 47 of the code the output array is used to merge the left and right half and is later used to overwrite the input array. This takes O(nlogn) extra space which is not constant.

phishman3579 commented

@timiscoding Thanks for the note. I initially coded it using extra space with the assumption that I'd get back to it at a later stage and code an in-place version; I obviously forgot to get back to it. But your issue has brought it to my attention. So, I coded up an in-place version of merge sort and committed it.