Apx: In-place Merge Sort

Merge Sort, historically in the textbook had been introduced as a subpar sorting algorithm. Although it having a few prestige properties like being stable and having no degraded performance edge.

It had been known as being less space-efficient, due to the required use of auxiliary array from the merging/conquer process.

An in-place, stable, worst O(n log n) sorting algorithm is longly regarded as the holy grail of sorting (reference: Coursera - Algorithms |)

Due the allocation nature of merge sort, and the absence of a holy grail sorting algorithm. Quick Sort still had long been seen as the most and only optimal sorting algorithm.

However, does the story necessary had to end like that 🤔?

If we think about it, the last missing step of being able to come up with an in-place merge sort. Is for us to find a $O(n)$function that could merge 2 sorted ranged from an array in-place.

Meanwhile, if we were to do some additional time researching, the best thing we have is std::ranges::inplace_merge in C++. Which still only operates in $O(N*log N)$time.

For future self, here were all the references I've gathered for this particular topic. (in-place merge sort/efficient in-place merge)

• StackOverflow: Post which claimed to have implemented $O(N)$, $O(1)$ range merging.

• StackOverflow: How to sort in-place using the merge sort algorithm

• StackExchange: Worst case 𝑂(𝑛 log 𝑛) in place stable sort?

• StackOverflow: Stable and in-place sorting algorithm?

• StackOverflow: Regarding in-place merge in an array

• StackOverflow: Quicksort vs. In-place Merge Sort

---

Fast forward in time, as for 2024. There had now been several practical algorithm that can achieve $O(N)$,$O(1)$ as well as being stable.

Several new algorithms were now being regarded as the Block Merge Sort Family, Wiki Sort, Grail Sort and Block Sort itself now being seen as a new generation of space & time efficient sorting algorithms.

Notable References

• GitHub: BonzaiThePenguin/WikiSort

• GitHub: HolyGrailSortProject/Rewritten-Grailsort

• YouTube: The Perfect Sorting Algorithm?? Block Sort Explained (Wiki Sort, Grail Sort)

• Rust: Unallocating stable sort

• GitHub: Use grailsort for sort_unstable

• ACM: Practical in-place merging

• In-Place Sorting With Merge Sort