бульбашкова сортування
Алгоритм цієї сортування полягає в послідовному порівнянні та зміні місць (якщо необхідно) пар сусідніх елементів масиву. Процес триває до тих пір, поки обміни не припиняться. Складність алгоритму також становить 
.
Легко бачити, що послідовний облік результатів попереднього порівняння (послідовне спливання "бульбашок") не допускає розпаралелювання. Алгоритм потребує модифікації.
Для ефективного розпаралелювання на процесорі EPIC -Архітектура необхідно при одному огляді масиву відокремити процедуру порівняння елементів і формування значень предикатів від процедури пересилання, тобто організувати множинне спливання "бульбашок".
Для цього при кожному огляді поточний (частково впорядкована) безліч елементів розбивається на пари. При першому (непарному) огляді перша пара включає перший елемент масиву. При другому (парному) огляді групування починається з другого елементу і т.д. Усередині пар елементи упорядковуються, при необхідності міняючись місцями так, щоб зліва стояв менший елемент. Наявність обмінів з кожним переглядом фіксується. Їх припинення свідчить про закінчення сортування масиву.
Нижче по кроках (оглядам) відображена сортування раніше розглянутого масиву. Формуються на кожному кроці пари елементів виділені. При парному n непарні кроки сортування вимагають аналізу k = n / 2 пар елементів, парні кроки вимагають аналізу k = (n / 2) - 1. При непарному nk = [n / 2] пар елементів.
План програми (внутрішній цикл розгорнуто) представлений на Мал. 8.3 . тут 
; індексація виконана з урахуванням поперемінного формування пар сусідніх елементів і з урахуванням їх перейменування після пересилання; k - індекс останньої аналізованої пари елементів; 
- предикат, що приймає значення "1", якщо операція, при якій він вказаний, виконується. Передбачається, що при виході за кордон масиву операція над елементами не проводиться. Далі передбачається можливість взаємного обміну даними, ініційована в одному командному слові.
Мал.8.3.
План програми бульбашкового сортування
Програма не передбачає використання умовних переходів і відповідає "теоретичної" складності, хоча час виконання алгоритму при даній комплектації АЛУ скорочується майже в чотири рази в порівнянні з застосуванням одного ІУ.
Сортування Шелла
Даний метод відноситься до "поліпшеним". Він передбачає послідовні етапи розбиття вихідного масиву на кілька груп і їх незалежну сортування.
Однак слід з обережністю ставитися до "поліпшеним" методам сортування, що вимагає значних підготовчих робіт і орієнтованим на людину - обчислювача, для якого логічний аналіз дій не буде складно, а тому виноситься за область обліку трудомісткості. У комп'ютерній програмі повинно бути все враховано за допомогою формалізованих дій.
На раніше обраному масиві продемонструємо сортування Шелла.
Спочатку виконується четверная сортування: групуються і сортуються елементи масиву, віддалені один від одного на відстані 4. Розглянутий масив буде розбитий на чотири групи елементів: A1 = {6, 4, 5}, A2 = {2, 7, 8}, A3 = {4, 10, 0}, A4 = {3, 9, 1}. Кожна група сортується одним з відомих способів. Елементи повертаються в масив з дотриманням тих же почала і відстані, з якими вони витягали. Тоді результатом четверний сортування буде послідовність 4, 2, 0, 1, 5, 7, 4, 3, 6, 8, 10, 9.
На другому проході елементи отриманої послідовності перегруповуються - тепер кожен елемент групи відстоїть від іншого на дві позиції. В даному випадку сформуються дві групи: B1 = {4, 0, 5, 4, 6, 10} і B2 = {2, 1, 7, 3, 8, 9}. Сортування всередині груп (подвійна сортування) і повернення в початковий масив на відповідні місця призводять до послідовності 0, 1, 4, 2, 4, 3, 5, 7, 6, 8, 10, 9.
На третьому проході остаточно виробляється звичайна (одинарна) сортування всієї послідовності, при якій число пересилань зведено до мінімуму.
Дослідження по вибору відстаней привели до теоретичного обгрунтування оцінки складності алгоритму, як O (n1,2). Ця складність заснована на мінімізації необхідних пересилань.
Цілком очевидно, що істотно ускладнюється логіка програми. Крім того, якщо на закінчення все одно необхідно виконати одиничну сортування, то при плануванні спекулятивного режиму в рамках предикатних обчислень абсолютно байдуже, чи виконується операція пересилання, на яку виділено час і кошти, чи ні. Так що дійсна складність алгоритму, що досягається на комп'ютері, значно перевершує складність алгоритмів сортування, розглянутих раніше.
Застосування даного методу, очевидно, недоцільно на процесорі EPIC -Архітектура.
<
