I was researching whether or not Quicksort is better than Merge Sort, and most sources were in consensus that Quicksort is better, because it is in-place, while Merge Sort is not. However, there exist in-place Merge Sort algorithms, which invalidate the "it needs extra space" argument. So which is better, Quicksort or In-place Merge Sort?
PS: When I say better, I mean faster, since space is not an issue for either of these sorts.
EDIT: Is any speed lost when switching from out-of-place Merge Sort to in-place Merge Sort?
The common implementation of in place merge sort is recursive, and quicksort is recursive, or both use some form of stack, so there is stack space used, O(log2(n)) for merge sort, and quicksort can also be restricted to O(log2(n)) by only using recursion on the smaller part after a partition step and looping for the large part, but time complexity can still be O(n^2) worst case.
The common in place merge sort is slower and also not stable. There are versions of merge sort that are in place and stable, but these are slow.
The algorithm for common in place merge sort is to sort the second half and the first quarter of an array, leaving the second quarter of the array unsorted. Then the first quarter and second half are merged into the array starting at the second quarter. Each time an element is merged, rather than moving it, that element is swapped, so what was the non-sorted data in the second quarter gets scattered about the sorted parts during a merge step (which is why this algorithm is not "stable"). When the merge step is completed, all of the unordered elements end up in the first quarter, with the rest of the array sorted. Next the first eighth of the array is sorted, and then the first eight and last 3 quarters are merged into the second eighth of the array, leaving the first eighth with unsorted data and the rest of the array sorted. This process is continued until there are only two unsorted elements on the left side of the array. These two elements are moved into place using insertion sort.
Note that this is not a stable sort.
Update - A block merge sort is stable and in place with time complexity O(n log(n)), but with lower order factors that make it slower than a normal merge sort that uses a second buffer. It works best if there are at least 2 · sqrt(n) unique values, which allows them to be re-ordered to provide working areas of an array and remain stable.