Слияние сорт как народный танец

Этот вид танца теперь дошел до сортировки слиянием, и это очень сложно — как он заканчивается парой мальчик-девочка?

Да, команда из Университета Sapientia все еще танцует алгоритмы сортировки, но пока нет никаких признаков быстрой сортировки, хотя это было обещано. Если вы хотите увидеть их четыре исходных танца сортировки, см. Алгоритмы сортировки как танцы. На этот раз у нас есть для вас сортировка слиянием.

В хранилище слияния список рекурсивно делится на два списка до тех пор, пока вы не дойдете до списка, состоящего из одного элемента (танцора), а затем каждый список объединяется, чтобы создать список, вдвое превышающий его размер, путем взятия элементов из пар подсписок по порядку . Итак, если у вас есть два списка [5] и [3], вы берете 3, а затем 5, чтобы получить список [3,5]. Если у вас есть два списка [3,5] и {2,8], вы берете 2 из второго списка, затем 3 из первого списка, затем 5 из первого и 8 из второго, чтобы получить [2 , 3,5,8] и так далее.

Слияние намного легче увидеть, когда у вас есть два больших частично отсортированных списка, что происходит ближе к концу танца, когда мальчики сливаются с девушками — как это получилось! И еще важнее, как получается, что в финальном слиянии каждый мальчик оказывается с девочкой?

Ах, какая сложность и сюрреализм — это танец …

Если вы хотите узнать подробности сортировки слиянием с точки зрения программиста, см .: Магия слияния.

Мы терпеливо ждем Quicksort, но все равно не думаем, что это танцевально …

Обновление 2 мая 2011 г.

Они доказали, что я ошибаюсь … все, что нужно для Quicksort как венгерского танца, — это пара шляп: наконец — Quicksort the dance