Кіріспе
Бірнеше реттелген тізімдерді біріктіретін алгоритм – кіріс ретінде бірнеше реттелген тізімдерді қабылдап, кіріс тізімдерінің барлық элементтерін реттелген түрде қамтитын жалғыз тізімді шығаратын алгоритмдер отбасы. Бұл алгоритмдер әртүрлі сұрыптау алгоритмдерінде, ең белгілісі – біріктіру сұрыптауында қосалқы бағдарлама ретінде қолданылады.
Merge algorithms are a family of algorithms that take multiple sorted lists as input and produce a single list as output, containing all the elements of the inputs lists in sorted order. These algorithms are used as subroutines in various sorting algorithms, most famously merge sort.
Қолдану
Бірлесу алгоритмі салыстыруға негізделген сұрыптау алгоритмінде маңызды рөл атқарады. Теориялық тұрғыдан алғанда, біріктіру сұрыптау алгоритмі екі қадамнан тұрады: тізімді (шамамен) бірдей ұзындықтағы кіші тізімдерге рекурсивті түрде бөліңіз, әрбір кіші тізімде тек бір элемент қалғанға дейін, немесе итеративтік (төменнен жоғарыға) біріктіру сұрыптау жағдайында n элементтен тұратын тізімді n бірлік өлшемді кіші тізімдер ретінде қарастырыңыз. Бір элементтен тұратын тізім, анықтама бойынша, сұрыпталған болып есептеледі. Барлық элементтер бір тізімде жиналғанша, жаңа сұрыпталған кіші тізімдерді құру үшін кіші тізімдерді қайта-қайта біріктіріңіз. Соңғы тізім – сұрыпталған тізім. Бірлесу алгоритмі біріктіру сұрыптау алгоритмінде бірнеше рет қолданылады. Мысал ретінде біріктіру сұрыптауын иллюстрацияда қараңыз. Ол 7 бүтін санды қамтитын сұрыпталмаған массивтен басталады. Массив 7 бөлікке бөлінеді; әр бөлікте 1 элемент болады және сұрыпталады. Сұрыпталған бөліктер одан әрі ірі, сұрыпталған бөліктерді жасау үшін біріктіріледі, сонгы сұрыпталған массив қалғанға дейін.
Recursively divide the list into sublists of (roughly) equal length, until each sublist contains only one element, or in the case of iterative (bottom up) merge sort, consider a list of n elements as n sub lists of size 1. A list containing a single element is, by definition, sorted. Repeatedly merge sublists to create a new sorted sublist until the single list contains all elements. The single list is the sorted list. The merge algorithm is used repeatedly in the merge sort algorithm. An example merge sort is given in the illustration. It starts with an unsorted array of 7 integers. The array is divided into 7 partitions; each partition contains 1 element and is sorted. The sorted partitions are then merged to produce larger, sorted, partitions, until 1 partition, the sorted array, is left.
Екі тізімді қатар біріктіру
Сондай-ақ екі сұрыпталған тізімді біріктірудің бір ғана мысалында параллелизмді енгізетін алгоритмдер бар. Бұларды бағдарламаланатын қақпалық массивтерде (FPGA), арнайы сұрыптау тізбектерінде, сондай-ақ бір нұсқаулық көп дерек (SIMD) нұсқаулары бар қазіргі заманғы процессорларда қолдануға болады. Қазіргі параллель алгоритмдер битондық сұрыптағыштың немесе тақ-тік біріктірудің біріктіру бөлігіне енгізілген өзгертулерге негізделген. 2018 жылы Saitoh M. және басқалар FPGA үшін MMS енгізді, ол аппараттық құралдарда тиімді конвейерленуге кедерес келтіретін көп циклді кері байланыс деректер жолын жоюға бағытталған. Сондай-ақ 2018 жылы Papaphilippou P. және басқалар FLiMS енгізді.
Python-тың атауы
Python стандартты кітапханасы (2.6 нұсқасынан бастап) `heapq` модулінде бірнеше рет сұрыпталған итерацияланатын объектілерді қабылдап, оларды бір итераторға біріктіретін функцияны қамтиды.