Декомпозиция әдісі

Көптеген пайдалы алгоритмдердің құрылымы рекурсивті болып келеді: белгілі есепті шешу үшін олар өз өзін рекурсивті бір немесе бірнеше рет шақырады, Мұндай алгоритмдер көбіне декомпозиция немесе бөлу әдістерінің көмегімен жасалады: күрделі есептер бірнеше қарапайым есептерге бөлінеді, олар берілген есепке ұқсас келеді, бірақ көлемі аз болады; кейіннен осы қосымша есептер рекурсивті әдіспен шешіледі, кейіннен алынған шешімдер берілген есептің шешімін табу мақсатында қосылады(комбинируется).

“бөліп ал да басқар” декомпозиция әдісі негізінде жатқан парадигма рекурсияның әрбір деңгейінде 3 этаптан өтеді.

Бөлу: есепті бірнеше кіші есептерге бөлу.

Бағындыру – алдыңғы кіші есептерді рекурсивті шешу. Кіші есептің көлемі жеткілікті аз болса, бөлінген кіші есептер тікелей шешіледі.

Қосу(комбинирование)- қосымша есептердің шешімдері арқылы берілген есептің шешімін шығару.

Біріктіріп сорттау (merge sort) алгоритмі бөлу әдісінің парадигмасына сәйкес келеді. Оның жұмысын төмендегідей сипаттауға болады.

Бөлу: сұрыпталатын n элементтен тұратын тізбек кішірек екі тізбекке бөлінеді, олардың әрбірінде n/ 2 элементтен тұрады.

Бағындыру: екі қосымша тізбек те біріктіру әдісімен сұрыпталады.

Қосу(комбинирование): екі сұрыпталған тізбекті біріктіріп соңғы шешімді аламыз.

Рекурсия сұрыпталатын тізбектің ұзындығы 1-ге тең болған кезде өзінің төменгі шегіне жетеді. Бұл жағдайда барлық жұмыс істелінді деп есептеледі, себебі мұндай тізбек реттелген деп есептеледі.

Біріктіру әдісі арқылы сұрыптау барысында орындалатын негізгі операция, ол –қосу барысында екі сұрыпталған тізбектерді біріктіру.