D04.9. Advantages and disadvantages of Merge Sort

[AndriyBosik]

D04.9. Advantages and disadvantages of Merge Sort D04.9. Переваги та недоліки Merge Sort

[AndriyBosik]

These were discussed during the lecture:

Advantages:

• It's fast O(n log n)
• is not vulnerable
• stable
• you can divide the sorting of subarrays into separate threads
• can be used to sort linked sheets

Disadvantages:

• requires additional memory
• works the same time
• even if the array is almost sorted
• not fast enough

Це було обговорено під час лекції:

Переваги:

• швидко працює O(n log n)
• не є вразливим
• cтабільний
• можна розбити сортування підмасивів на окремі треди
• може використовуватися для сортування лінкед лістів

Недоліки:

• потребує додаткової пам'яті
• працює однаковий час
• навіть якщо масив майже відсортований
• не достатньо швидкий

[AndriyBosik]

Discussion from previous years:

Advantages:

• Nothing good
• Sorts - already good ☺
• Faster than a bubble

Disadvantages:

• Long?
• Not adaptive
• Additional memory

Обговорення з попередніх років:

Переваги

• Нічого хорошого
• Сортує – вже добре ☺
• Швидше ніж bubble

Недоліки

• Довго?
• Не адаптивний
• Додаткова пам’ять

[glbter]

Переваги

• теоретичний інтерес (хоча ідея поділу не нова, та над злиттям результатів треба подумати, при першій реалізації)

Недоліки

• за рахунок додаткової пам'яті ще більше пожирає стек, ніж наприклад quick sort

[RedBarboriska]

Переваги

• Може застосовуватися для файлів будь-якого типу
• Працює швидше для великих списків, оскільки на відміну від insertion та bubble sort, він не проходить весь список декілька разів.
• Починається з менших підфайлів і закінчується найбільшими. В результаті йому не потрібен стек => стабільний
• Складність практично завжди o (n log (n)), що робить його досить ефективним

Недоліки

• Потрібні додаткові витрати пам'яті n
• Працює повільніше порівняно з іншими алгоритмами для сортування малої кількості елементів.

[ZinchenkoArtem1]

Advantage of merge sort

• Good for sorting slow-access data e.g. tape drive or hard disk.
• It is excellent for sorting data that are normally accessed sequentially. e.g. linked lists, tape drive, hard disk and receiving online data one item at a time

Disadvantages

• In many implementations, if the list is N long, then it needs 2 x N memory space to handle the sort.
• If recursion is used to code the algorithm then it uses twice as much stack memory as quicksort - on the other hand it is not difficult to code using iteration rather than recursion and so avoid the memory penalty.
• Quicksort is considered the fastest method on most types of lists.

[Edward3635]

Переваги алгоритму: 1.Поєднується з механізмом кешування пам'яті. 2.Працює в паралельному варіанті: легко розбити завдання між процесорами . 3.Якщо один процесор затримається, решта беруть його роботу на себе. Недоліки алгоритму: На «майже відсортованих» масивах працює з такою швидкістю, як на хаотичних. Складність O(n log n)

[YevgeniyBukur]

Advantages:

sustainable You can write efficient multi-threaded merge sort, sorting of data located on peripheral devices and not fit in RAM.

Disadvantages:

additional O (n) memory is required, but can be modified to O (1).

[kzhereb]

Недоліки

• за рахунок додаткової пам'яті ще більше пожирає стек, ніж наприклад quick sort

Додаткова пам'ять зазвичай виділяється на heap, тому не впливає на розмір стеку