Практическое использование сортировки места на месте

Question

Я попробовал поиск здесь и там, чтобы узнать, что именно происходит на месте слияния и где мне нужно его использовать? Но не нашел прямого ответа. Пожалуйста, помогите мне, ответив ниже.

1) Когда и где требуется слияние на месте? Практическое использование слияния на месте.

2) Что произойдет, если входные массивы для слияния на месте не отсортированы?

3) Что ест больше памяти для сортировки между сортировкой Merge, сортировкой на месте и быстрой сортировкой?

Примечание: Я прошу относительно «std :: inplace_merge», который является алгоритмом stl.

Answer 1

1) Сортировка слияния на месте используется, если вы хотите отсортировать список по времени O (nlogn), используя меньшее пространство, чем стандартное объединение.

2) Вся цель сортировки состоит в том, чтобы сортировать входные массивы, поэтому не отсортированные массивы ввода будут отсортированы по месту объединения.

3) Mergesort использует больше памяти, потому что он создает два новых массива половинного размера для двух рекурсивных вызовов. Сортировка слияния на месте и быстрая сортировка должны занимать одно и то же пространство, потому что они оба на месте. Для mergesort, in-place означает O (log n) дополнительное пространство от хранения соответствующих индексов массива длины n, а не строгое значение O (1) на месте. Quicksort занимает O (nlogn) дополнительное пространство в худшем случае, так как могут быть рекурсивные вызовы O (n), каждый из которых имеет указатели, которые занимают пространство O (logn).

Надеюсь, это поможет.