就地归并排序实际用法 [英] In-place merge sort practical usage

问题描述

我试着到处搜索，以找出到底什么是就地合并排序，以及我需要在哪里使用它？但没有找到一个直接的答案。请在下面回答以帮助我。

1)何时何地需要就地合并？就地合并的实际用法。

2)如果未对就地合并的输入数组进行排序，会发生什么情况？

3)在合并排序、就地合并排序和快速排序中，哪种排序占用的内存更多？

注意：我问的是关于"std：：inplace_merge"的问题，这是一种stl算法。

推荐答案

1)如果要在O(Nlogn)时间内对列表进行排序，而使用的空间比标准合并排序少，则使用就地合并排序。

2)排序的全部目的是对输入数组进行排序，因此未排序的输入数组将按就地合并排序。

3)Mergesort使用更多内存，因为它为两个递归调用创建了两个大小减半的新数组。就地合并排序和快速排序应该占用相同的空间，因为它们都是就地排序。对于合并排序，In-Place意味着保留长度为n的数组的相关索引的O(Logn)额外空间，而不是最严格的In-Place的O(1)含义。快速排序在最坏的情况下会占用O(Nlogn)个额外空间，因为可能有O(N)个递归调用，每个递归调用都有占用O(Logn)空间的指针。

希望这能有所帮助。

这篇关于就地归并排序实际用法的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！