Mergesort: Редакция

Question

Работает ли сортировка слиянием;

взятие списка значений

разделив его на два

взять первый элемент каждого списка, самое низкое значение которого входит в новый список (и я думаю, что удалены из оригинала). Сочетайте следующие два числа - делайте это, пока один список не станет пустым, затем поместите оставшуюся часть другого списка в конец списка nw?

Кроме того, каковы последствия этого в связанном списке?

Спасибо

Answer 1

То, что вы описали, это только слияние (без сортировки), сортировка выполняется рекурсивно в сортировке слиянием.

Also, what are the ramifications of doing this on a linked list?

Вероятно, слишком дорого разделять связанные списки, если у вас есть два отсортированных списка, вы можете легко объединить их, сохраняя порядок.

Answer 2

Сортировка слиянием работает, разбивая массив на две части, затем вызывая сортировку слиянием для каждой половины. Когда сортировка слиянием вызывается только с одним элементом, она просто возвращает его. Объединение происходит после рекурсии и собирает массив обратно в отсортированном порядке.

array mergesort(array)
{
    if(array.len == 1) return array;

    array temp1 = mergesort(array.firsthalf);
    array temp2 = mergesort(array.secondhalf);

    return merge(temp1, temp2);
}

Проблема применения сортировки слиянием к связанному списку состоит в том, что у вас нет простого способа разбить его пополам. Вам придется повторяться, пока не дойдете до половины пути. Это потребует дополнительного времени и неоправданно повлияет на производительность сортировки слиянием. С массивом вы можете выполнять простые целочисленные операции с постоянным временем, чтобы разделить его на две части.