Кіріспе
Бөліп-басқару сұрыптау алгоритмі
Компьютерлік ғылымда біріктіру сұрыптау (сонымен қатар, біріктіру деп те жазылады) – тиімді, жалпы мақсаттағы және салыстыру негізінде жұмыс істейтін сұрыптау алгоритмі. Көптеген іске асырулар тұрақты сұрыптауды қамтамасыз етеді, яғни бірдей элементтердің бастапқы және соңғы реттері бірдей болады. Біріктіру сұрыптау – 1945 жылы Джон фон Нейман тапқан бөліп-басқару алгоритмі. 1948 жылы Голдстин мен фон Нейманның есебінде төменнен жоғарыға қарай біріктірудің толық сипаттамасы мен талдауы жарияланды.
Пинг-понгты біріктіру сұрыптау
Бір уақытта екі блокты біріктірудің орнына, пинг-понг біріктіру бір уақытта төрт блокты біріктіреді. Төрт реттелген блок бір мезгілде қосалқы жадқа екі реттелген блокқа біріктіріледі, содан кейін екі реттелген блок негізгі жадқа қайта біріктіріледі. Осылай істеу көшіру операциясын болдырмайды және жалпы қозғалыстар санын екі есеге азайтады. Төрт блокты бірден біріктірудің алғашқы, ашық қолданыстағы іске асырылуы 2014 жылы WikiSort жүзеге асырды, бұл әдіс сол жылы шыдамдылық сұрыптауын оңтайландыру ретінде сипатталды және пинг-понг біріктіру деп аталды. Quadsort 2020 жылы осы әдісті іске асырып, квадро біріктіру деп атады.
Бірлескен орындар сұрыптау
Бірлесу сұрыптамасының массивтерде іске асырылғандағы бір кемшілігі – O(n) жұмыс жады қажеттілігі. Жадыны азайту немесе бірлесу сұрыптамасын толыққанды орнында орындау үшін бірнеше әдіс ұсынылды: бірлесу сұрыптамасының тұрақты қосымша кеңістік қолданатын баламалы нұсқасы ұсынылды. Katajainen және басқалар жұмыс жадының тұрақты көлемін қажет ететін алгоритм ұсынды: кіріс массивінің бір элементін сақтауға жеткілікті жад және кіріс массивіне O(1) сілтемелерді сақтауға қосымша орын. Олар кішігірім тұрақтылармен O(n log n) уақытқа жетеді, бірақ олардың алгоритмі тұрақты емес. Стандартты (жоғарыдан төменге немесе төменнен жоғарыға) бірлесу сұрыптамасымен біріктірілетін орнындағы бірлесу алгоритмін жасауға бірнеше әрекеттер жасалды. Бұл жағдайда «орнында» түсінігін «лог. қапшық кеңістігін пайдалану» деп жеңілдетуге болады, өйткені стандартты бірлесу сұрыптамасы өзінің қапшықтары үшін осы кеңістікті қажет етеді. Geffert және басқалар көрсеткендей, тұрақты мөлшерде қосымша жадты пайдалана отырып, орнындағы тұрақты бірлесу O(n log n) уақытында мүмкін, бірақ олардың алгоритмі күрделі және жоғары тұрақты факторлары бар: n және m ұзындығындағы массивтерді біріктіру 5n + 12m + o(m) амалға соғады. Бұл жоғары тұрақты фактор және күрделі алгоритм қарапайымдатылып, түсінікті етілді. Bing Chao Huang және Michael A. Langston қосымша кеңістіктің белгілі бір мөлшерін пайдалана отырып, сұрыпталған тізімді біріктіруге арналған тікелей сызықтық уақытты алгоритм ұсынды. Олардың екеуі де Kronrod және басқалардың еңбектерін пайдаланды. Ол сызықтық уақытта және тұрақты қосымша кеңістікте бірігеді. Алгоритм стандартты бірлесу сұрыптамасы алгоритмдеріне қарағанда орташа уақыттан азырақ алады, O(n) уақытша қосымша жад ұяларын екі еседен аз фактормен пайдалануға болады. Алгоритм практикалық тұрғыдан әлдеқайда жылдам болғанымен, кейбір тізімдер үшін тұрақсыз. Бірақ ұқсас түсініктерді қолдану арқылы олар бұл мәселені шеше алды. Басқа орнындағы алгоритмдердің ішінде SymMerge бар, ол O((n + m) log (n + m)) уақыт алады және тұрақты. Мұндай алгоритмді бірлесу сұрыптамасына қосу оның күрделігін сызықтық емес, бірақ әлі де квазилинейлік O(n (log n)^2) дейін арттырады. Сыртқы сұрыптаудың көптеген қолданбалары кіріс деректерін үлкен саны қосалқы тізімдерге бөлетін бірлесу сұрыптамасының түрін қолданады, идеалды жағдайда оларды біріктіру қазіргі уақытта өңделіп жатқан беттер жиынтығын негізгі жадқа сыйдыратын санға дейін. Қазіргі заманғы тұрақты сызықтық және орнындағы бірлесу нұсқасы – блоктарды бірлесу сұрыптамасы, ол алмасу кеңістігі ретінде пайдалануға арналған бірегей мәндер бөлімін жасайды. Екілік іздеулер мен айналымдарды пайдалану арқылы үстеме кеңістігі sqrt(n) дейін азайтылуы мүмкін. Бұл әдіс C++ STL кітапханасы және квадсортпен қолданылады. Кейбір үстеме шығындармен жоғарыда аталған алгоритмді үш таспаны пайдалану үшін өзгертуге болады. O(n log n) жұмыс уақытын екі кезек, немесе стек және кезек, немесе үш стек арқылы да қол жеткізуге болады. Керісінше, k > екі таспаны (және жадта O(k) элементін) пайдаланып, k/2 жолды біріктіру арқылы O(log k) есеге дейін таспа операцияларының санын азайтуға болады. Таспаны (және дискіні) пайдалануды оңтайландыратын күрделі бірлесу сұрыптамасы – полифазалық бірлесу сұрыптамасы.
suggested an alternative version of merge sort that uses constant additional space. Katajainen et al. present an algorithm that requires a constant amount of working memory: enough storage space to hold one element of the input array, and additional space to hold O(1) pointers into the input array. They achieve an O(n log n) time bound with small constants, but their algorithm is not stable. Several attempts have been made at producing an in place merge algorithm that can be combined with a standard (top down or bottom up) merge sort to produce an in place merge sort. In this case, the notion of "in place" can be relaxed to mean "taking logarithmic stack space", because standard merge sort requires that amount of space for its own stack usage. It was shown by Geffert et al. that in place, stable merging is possible in O(n log n) time using a constant amount of scratch space, but their algorithm is complicated and has high constant factors: merging arrays of length n and m can take 5n + 12m + o(m) moves. This high constant factor and complicated in place algorithm was made simpler and easier to understand. Bing Chao Huang and Michael A. Langston presented a straightforward linear time algorithm practical in place merge to merge a sorted list using fixed amount of additional space. They both have used the work of Kronrod and others. It merges in linear time and constant extra space. The algorithm takes little more average time than standard merge sort algorithms, free to exploit O(n) temporary extra memory cells, by less than a factor of two. Though the algorithm is much faster in a practical way but it is unstable also for some lists. But using similar concepts, they have been able to solve this problem. Other in place algorithms include SymMerge, which takes O((n + m) log (n + m)) time in total and is stable. Plugging such an algorithm into merge sort increases its complexity to the non linearithmic, but still quasilinear, O(n (log n)^(2)). Many applications of external sorting use a form of merge sorting where the input get split up to a higher number of sublists, ideally to a number for which merging them still makes the currently processed set of pages fit into main memory. A modern stable linear and in place merge variant is block merge sort which creates a section of unique values to use as swap space. The space overhead can be reduced to sqrt(n) by using binary searches and rotations. This method is employed by the C++ STL library and quadsort. With some overhead, the above algorithm can be modified to use three tapes. O(n log n) running time can also be achieved using two queues, or a stack and a queue, or three stacks. In the other direction, using k > two tapes (and O(k) items in memory), we can reduce the number of tape operations in O(log k) times by using a k/2 way merge. A more sophisticated merge sort that optimizes tape (and disk) drive usage is the polyphase merge sort.
Біріктірудің сұрыптауын оңтайландыру
Қазіргі заманғы компьютерлерде деректерге сілтеме жасаудың жергіліктілігі бағдарламалық қамтамасыз етуді оңтайландыруда маңызды рөл атқарады, себебі көп деңгейлі жад иерархиясы қолданылады. Машинаның жад кэшінде беттердің ішке және сыртқа қозғалысын азайтуға бағытталған, кэшке бейімделген біріктіру сұрыптау алгоритмінің нұсқалары ұсынылған. Мысалы, плиткалы біріктіру сұрыптау алгоритмі, субаррейлердің мөлшері S-ке жеткен кезде субаррейлерді бөлуді тоқтатады, мұнда S – процессордың кэшіне сыятын дерек элементтерінің саны. Бұл кіші массивлердің әрқайсысы жадтың ауысуын азайту үшін, орнында сұрыптау алгоритмімен, мысалы, енгізу сұрыптаумен сұрыпталады, содан кейін стандартты рекурсивті әдіспен біріктіру сұрыптау аяқталады. Бұл алгоритм кэшті оңтайландырудан пайда көретін машиналарда жақсы нәтижелер көрсетті.
Қатарлас біріктіру сұрыптау
Біріктіру сұрыптау, бөліп-бас иелену әдісін пайдалану арқасында жақсы параллельделеді. Жылдар бойы алгоритмнің әртүрлі параллель түрлері жасалды. Кейбір параллель біріктіру сұрыптау алгоритмдері тікелей жоғарыдан төменге біріктіру алгоритмімен байланысты, ал басқалары мүлдем басқа құрылымға ие және K-жолды біріктіру әдісін қолданады.
Қатарлас біріктіру арқылы біріктіру сұрыптау
Параллельдікке жақсырақ қол жеткізу үшін параллель біріктіру алгоритмін пайдалануға болады. Кормен және авторлар екі реттелген кіші тізбекті бір реттелген шығыс тізбегіне біріктіретін екілік нұсқасын ұсынады.
Қатарлас көп жолды біріктіру сұрыптау
Біріктіру сұрыптау алгоритмдерін екілік біріктіру әдісімен шектеудің себебі түсініксіз, себебі көбінесе p > 2 процессор қол жетімді. Одан да жақсы тәсіл – K жолды біріктіру әдісін пайдалану, ол екілік біріктірудің жалпыланған түрі болып табылады, онда сұрыпталған тізбектер біріктіріледі. Бұл біріктіру түрі PRAM-дағы сұрыптау алгоритмін сипаттауға өте ыңғайлы.
Негізгі идея
Элементтердің ретсіз тізбесі берілгенде, мақсат – тізбекті қолданылатын процессорлармен реттеу. Бұл элементтер барлық процессорлар арасында тең бөлінеді және тізбекті реттеу алгоритмін пайдаланып, жергілікті түрде реттеледі. Сондықтан, тізбек ұзындығы реттелген тізбектерден тұрады. Жаңайтылған алгоритм үшін, глобальдық рангі бар бөлгіш элементтер анықталады. Содан кейін, әрбір тізбектегі бөлгіш элементтердің сәйкес келетін орналасуы екілік іздеу арқылы анықталады, осылайша тізбек ұзындығының ішкі тізбектерге бөлінуі жүзеге асырылады. Бұдан әрі, элементтер процессорға тағайындалады, яғни рангі мен рангі арасындағы барлық элементтер, олардың барлығы бөліседі. Осылайша, әрбір процессор реттелген тізбектердің тізбесін алады. Бөлгіш элементтерінің рангі жалпы түрде таңдалғандықтан, екі маңызды қасиет қамтамасыз етіледі: Біріншіден, әрбір процессор тағайындалғаннан кейін де элементтермен жұмыс істей алуы үшін бөлгіш элементтер таңдалды. Алгоритмнің жүктемесі толыққанды теңгерілген. Екіншіден, процессордағы барлық элементтер басқа процессордағы барлық элементтерден кем немесе тең болады. Сондықтан, әрбір процессор p-жолды біріктіруді жергілікті түрде орындайды және осылайша кіші тізбектерінен реттелген тізбек алады. Екінші қасиеттің арқасында, одан әрі p-жолды біріктіруді орындау қажет емес, нәтижелер тек процессор нөмірінің ретімен біріктірілуі керек.
These sequences will be used to perform a multisequence selection/splitter selection. For , the algorithm determines splitter elements with global rank Then the corresponding positions of in each sequence are determined with binary search and thus the are further partitioned into subsequences with
Furthermore, the elements of are assigned to processor , means all elements between rank and rank , which are distributed over all Thus, each processor receives a sequence of sorted sequences. The fact that the rank of the splitter elements was chosen globally, provides two important properties: On the one hand, was chosen so that each processor can still operate on elements after assignment. The algorithm is perfectly load balanced. On the other hand, all elements on processor are less than or equal to all elements on processor Hence, each processor performs the p way merge locally and thus obtains a sorted sequence from its sub sequences. Because of the second property, no further p way merge has to be performed, the results only have to be put together in the order of the processor number.
Талдау
Біріншіден, әрбір процессор тағайындалған элементтерді жергілікті түрде күрделілігі бар сұрыптау алгоритмін қолдана отырып сұрыптайды. Содан кейін, бөлгіш элементтер уақыттың ішінде есептелуі керек. Әрі қарай, әрбір топтағы бөліністер әрбір процессормен параллель түрде қатарлы p жолды біріктіру алгоритмін қолдана отырып біріктірілуі керек. Осылайша, жалпы жұмыс уақыты келесідей беріледі: .
.
Іс жүзінде қолдану және қолдану
Көп жолды біріктіру сұрыптау алгоритмі жоғары параллельдеу мүмкіндігі арқасында өте масштабталатындығымен ерекшеленеді, бұл көптеген процессорларды пайдалануға мүмкіндік береді. Бұл алгоритмді компьютерлік кластерлерде өңделетін сияқты үлкен көлемдегі деректерді сұрыптау үшін тиімді кандидат етеді. Сондай-ақ, мұндай жүйелерде жад көбінесе шектеулі ресурс болмайтындықтан, біріктіру сұрыптаудың жадты пайдалану тиімсіздігі ескерілмейді. Дегенмен, PRAM-да модельдеу кезінде назарға алынбайтын басқа факторлар да маңызды болып табылады. Мұнда келесі аспектілерді қарастыру қажет: жад иерархиясы, деректер процессордың кэш-жадына сыймағанда немесе процессорлар арасында деректер алмасудың байланыс шығындары, бұл деректер ортақ жад арқылы қолжетімді болмай қалғанда бәсекелес болуы мүмкін. Сандерс және авторлар өз мақалаларында көп деңгейлі көп жолды біріктіру үшін бір уақытта орындалатын параллель алгоритм ұсынды, ол процессорларды белгілі бір мөлшердегі топтарға бөледі. Барлық процессорлар алдымен жергілікті түрде деректерді сұрыптайды. Бір деңгейлі көп жолды біріктіруден айырмашылығы, бұл тізбектер кейін бөліктерге бөлініп, тиісті процессор топтарына тағайындалады. Бұл қадамдар сол топтарда рекурсивті түрде қайталанады. Бұл байланыс көлемін азайтады және әсіресе көптеген шағын хабарламалармен туындайтын мәселелерден сақтануға көмектеседі. Негізгі нақты желінің иерархиялық құрылымы процессор топтарын анықтау үшін пайдаланылуы мүмкін (мысалы, тіреулер, кластерлер). Басқа да күрделі параллель сұрыптау алгоритмдері төменгі тұрақтылықпен бірдей немесе жақсырақ уақыт шектеріне қол жеткізе алады. Мысалы, 1991 жылы Дэвид Пауэрс параллельді жылдам сұрыптауды (және оған байланысты радикс сұрыптауды) сипаттады, ол n процессорлы CRCW параллельді кездейсоқ қолжетімділік машинасымен (PRAM) O(log n) уақытында жұмыс істей алады, бұл процесті бөлуді тікелей жүзеге асыру арқылы мүмкін болады. Пауэрс сондай-ақ Батчердің Bitonic Mergesort-тың құбырлы нұсқасының сары түсті сұрыптау желісінде O((log n)2) уақытында PRAM-дегі O(log n) сұрыптауларынан іс жүзінде жылдам болатынын көрсетіп, салыстыру, радикс және параллель сұрыптаудағы жасырын шығындарды егжей-тегжейлі талқылайды.
Басқа сұрыптау алгоритмдермен салыстыру
Heapsort біріктіру сұрыптамасымен бірдей уақыт шектеріне ие болғанымен, біріктіру сұрыптамасының Θ(n) орнына тек Θ(1) қосалқы кеңістік алады. Көбінесе қазіргі заманғы архитектураларда, RAM-ге негізделген массивтерді сұрыптау үшін тиімді жылдам сұрыптама жүзеге асырылымдары біріктіру сұрыптамасынан жақсы нәтиже береді. Деректердің сұрыпталуға тиіс көлемі кішкентай болғанда жылдам сұрыптама артықшылықты болады, себебі жылдам сұрыптаманың кеңістік күрделілігі O(log n) болып табылады, бұл кэш жадының тиімді пайдалануына біріктіру сұрыптамасынан (кеңістік күрделілігі O(n)) гөрі көбірек көмектеседі. Java-да Arrays.sort әдістері деректердің типіне байланысты біріктіру сұрыптамасын немесе жақсартылған жылдам сұрыптаманы қолданады, ал массивте жеті элементтен аз болғанда енгізу сұрыптамасына ауысып, тиімділікті арттырады. Linux ядросы байланысқан тізімдері үшін біріктіру сұрыптамасын пайдаланады. Timsort, біріктіру сұрыптамасы мен енгізу сұрыптамасының жақсартылған гибриді, Java және Android платформаларын қоса алғанда, әртүрлі бағдарламалық платформаларда және тілдерде қолданылады, ал бұрын Python 2.3 нұсқасынан 3.10 нұсқасына дейін қолданылды.