> For the complete documentation index, see [llms.txt](https://republic-of-cs.gitbook.io/e/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://republic-of-cs.gitbook.io/e/rcs.101/graduation/apx-in-place-merge-sort.md).

# Apx: In-place Merge Sort

{% hint style="info" %}
**Merge Sort**, historically in the textbook had been introduced as a subpar sorting algorithm. Although it having a few prestige properties like being [**stable**](https://en.wikipedia.org/wiki/Category:Stable_sorts) 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.
{% endhint %}

<figure><img src="https://550114503-files.gitbook.io/~/files/v0/b/gitbook-x-prod.appspot.com/o/spaces%2FV9kHdumiUo1ODZRtnI76%2Fuploads%2FqWd3x6ebal1xlXinb9Oi%2Fimage.png?alt=media&amp;token=fdcad18b-87dc-4df4-8adf-1417a9caac15" alt=""><figcaption><p>An in-place, stable, worst O(n log n) sorting algorithm is longly regarded as the holy grail of sorting<br>(reference: Coursera - Algorithms |)</p></figcaption></figure>

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.

{% hint style="info" %}

#### However, does the story necessary had to end like that :thinking:?

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**](https://en.cppreference.com/w/cpp/algorithm/ranges/inplace_merge) in C++. Which still only operates in $$O(N\*log N)$$time.
{% endhint %}

> 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.](https://stackoverflow.com/questions/4373307/is-it-possible-to-do-an-inplace-merge-without-temporary-storage)
> * StackOverflow: [How to sort in-place using the merge sort algorithm](https://stackoverflow.com/questions/2571049/how-to-sort-in-place-using-the-merge-sort-algorithm)
> * StackExchange: [Worst case 𝑂(𝑛 log 𝑛) in place stable sort?](https://cs.stackexchange.com/questions/2569/worst-case-on-ln-n-in-place-stable-sort)
> * StackOverflow: [Stable and in-place sorting algorithm?](https://stackoverflow.com/questions/62390325/stable-and-in-place-sorting-algorithm)
> * StackOverflow: [Regarding in-place merge in an array](https://stackoverflow.com/questions/3285756/regarding-in-place-merge-in-an-array)
> * StackOverflow: [Quicksort vs. In-place Merge Sort](https://stackoverflow.com/questions/50883815/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**](https://sortingalgos.miraheze.org/wiki/Block_Merge_Sort)**,** [**Wiki Sort**](https://github.com/BonzaiThePenguin/WikiSort)**,** [**Grail Sort**](https://sortingalgos.miraheze.org/wiki/Grailsort) and **Block Sort** itself now being seen as a new generation of space & time efficient sorting algorithms.

#### Notable References

* **GitHub:** [**BonzaiThePenguin/WikiSort**](https://github.com/BonzaiThePenguin/WikiSort)
* **GitHub:** [**HolyGrailSortProject/Rewritten-Grailsort**](https://github.com/HolyGrailSortProject/Rewritten-Grailsort)
* **YouTube:** [**The Perfect Sorting Algorithm?? Block Sort Explained (Wiki Sort, Grail Sort)**](https://www.youtube.com/watch?v=InGeRuRk3f8)
* **Rust:** [**Unallocating stable sort**](https://internals.rust-lang.org/t/unallocating-stable-sort/15834)
* **GitHub:** [**Use grailsort for sort\_unstable**](https://github.com/rust-lang/rust/issues/81842)
* **ACM:** [**Practical in-place merging**](https://dl.acm.org/doi/pdf/10.1145/42392.42403)
* [**In-Place Sorting With Merge Sort**](https://www.baeldung.com/cs/merge-sort-in-place)