Алгоритм сортировки слиянием на Java

Описание алгоритма:

  1. Сортируемый массив разбивается на две части примерно одинакового размера.
  2. Каждая из получившихся частей сортируется отдельно.
  3. Два получившихся упорядоченных массива соединяются в один. При этом наименьший из первых элементов двух массивов записывается в результирующий массив, и эта операция повторяется, пока не закончатся элементы в этих двух массивах.

Реализуем этот алгоритм на Java.

Внимание! Не следует писать алгоритмы сортировки самостоятельно для реальных приложений. Нужно использовать готовые алгоритмы для коллекций и методы из java.util.Arrays.

Итак, моя реализация сортировки слиянием на Java:

Достоинства:

  • Быстрый. Примерно O(n log n) операций.
  • Можно использовать на связанных списках.
  • Можно сделать реализацию, использующую параллельные потоки.
  • Сохраняет порядок равных элементов (устойчивая)

Недостатки:

  • На почти отсортированных массивах работает также, как и на неотсортированных.
  • Нужна дополнительная память для буфера.

Вам также может быть интересна быстрая сортировка и сортировка вставками.


Поделиться:
1 Звезда2 Звезды3 Звезды4 Звезды5 Звезд (Пока оценок нет)
Загрузка...

Один комментарий к “Алгоритм сортировки слиянием на Java”

Добавить комментарий

Ваш e-mail не будет опубликован.

*