Միաձուլման տեսակավորում

Միաձուլման տեսակավորում O(n log n), համեմատման վրա հիմնված տեսակավորման ալգորիթմ է։ Կատարման մեծ մասն արտադրում է ստաբիլ տեսակավորում, որը նշանակում է, որ կատարումը պաշտպանում է մուտքի հրամանը տեսակավորված ելքի հավասար էլեմենտներից։ Դա անջատ և նվաճված ալգորիթմ է։ Միաձուլումը հայտնաբերվել է 1945 թ.-ին Ջոն վոն Նյումանի կողմից
Goldstine:

Ալգորիթմ 
Միաձուլման տեսակավորման օրինակ։ Առաջին հերթին բաժանել էջը փոքրագույն մասնիկների, ապա համեմատել յուրաքանչյուր մասնիկ հարակից էջի հետ՝ տեսակավորելու և միավորելու երկու հարակից էջերը։ Արդյունքում բոլոր մասնիկները տեսակավորվում և միավորվում են իրար։ Միաձուլումը տեղի է ունենում հետևյալ կերպ՝
1. Եթե էջի լայնությունը 0 – ից 1 է, այն արդեն տեսակավորված է
2. Բաժանել չտեսակավորված էջը 2 ենթաէջերի՝ կես էջի չափով
3. Տեսակավորել յուրաքանչյուր ենթաէջը ռեկուրսիվ եղանակով առաջարկելով միաձուլում
4. Վերամիավորել 2 ենթաէջերը 1 տեսակավորված էջերի մեջ։

Միաձուլումը կազմի մեջ է մտցնում 2 հիմնական գաղափարները՝ արդարացնելու իր աշխատաժամանակը։
1. Փոքր էջն ավելի քիչ քայլեր կպահանջի միաձուլման համար, քան մեծ էջը։
2. Քիչ քայլերը նախատեսված են կառուցելու տեսակավորված էջ 2 տեսակավորված և 2 չտեսակավորված էջերից։ Օրինակ միայն պետք է հատել յուրաքանչյուր էջը մի անգամ, եթե դրանք արդեն տեսակավորված են։ 
Կիրառենք միաձուլումը տեսակավորելու integer –ների էջ, որը պարունակվում է զանգվածում։ Կիրառենք միաձուլումը տեսակավորելու integer – ների էջ։

Ենթադրենք ունենք A զանգված n ինդեքսով, որը դասավորված է A0 – ից An-1։ Մենք առաջարկում ենք միաձուլումը A (A0 ... Ac-1 ) և A (Ac... An-1), որտեղ c – ն n/ 2 – ի integer մասն է։ Երբ 2 կեսերը վերադարձվում են, դրանք պետք է տեսակավորվեն։ Դրանք այժմ կարող են միաձուլվել միմյանց հետ՝ կազմելով տեսակավորված զանգված։  to .

Հասարակ pseudocode ձևում ալգորիտմը կարող է ունենալ հետևյալ տեսքը՝

function merge_sort(m)
 if length(m) ≤ 1
 return m
 var list left, right, result
 var integer middle = length(m) / 2
 for each x in m up to middle
 add x to left
 for each x in m after middle
 add x to right
 left = merge_sort(left)
 right = merge_sort(right)
 result = merge(left, right)
 return result

 merge Ֆունկցիան պահանջում է և աջ և ձախ էջերի միաձուլում։ Այն ունի հետևյալ վարիացիաները՝

 function merge(left, right)
 var list result
 while length(left) > 0 or length(right) > 0
 if length(left) > 0 and length(right) > 0
 if first(left) ≤ first(right)
 append first(left) to result
 left = rest(left)
 else
 append first(right) to result
 right = rest(right)
 else if length(left) > 0
 append first(left) to result
 left = rest(left)
 else if length(right) > 0
 append first(right) to result
 right = rest(right)
 end while
 return result

Վերլուծություն
Կրկնվող միաձուլման ալգորիտմը սովորաբար տեսակավորում է 7 ինթեջեր արժողությամբ զանգված։ Միաձուլումն իրականացնելու համար պետք է հետևել հետևյալ քայլերին։

Տեսակավորման n միաձուլվող օբյեկտներն ունեն O(n log n ) – ի ներկայացման միջին և վատագույն դեպքեր։ Եթե n լայնության էջի միաձուլման ժամանակը T( n) է, T(n) = 2T(n/2) + n, որը հետևում է ալգորիթմի որոշիչին(առաջարկել սովորական էջի կեսի չափով 2էջի ալգորիթմ և ավելացնել n քայլեր, որոնք վերցված են միաձուլելու արդյունքային 2 էջերը )։ Փակ ձևը հետևում է վարպետ թեորեմից։ Տեսակավորման n միաձուլվող օբյեկտներն ունեն O(n log n ) – ի ներկայացման միջին և վատագույն դեպքեր։ Եթե n լայնության էջի միաձուլման ժամանակը T( n) է վատագույն դեպքի ներկայացում։
Վատագույն դեպքում ձեռնարկությունների թվի միաձուլումը հավասար կամ փոքր է ( n ⌈lg n⌉⌉ - 2⌈ lg n⌉+ 1), որը (n lg n- n + 1) - ի և (n lg n + n + O(lg n)) – ի միջև է։ Մեծ n- ի և հազվադեպ կարառվող մուտքի էջի համար միաձուլման ենթադրվող միջին համեմատության թիվը ավելի քիչ է մոտեցնում a n, քան վատագույն դեպքում։

Վատագույն դեպքում միաձուլումը կատարում է 39% պակաս համեմատություն, քան արագ տեսակավորումը կատարում է միջինի դեպքում։ Սակայն կան հատուկ դեպքեր, երբ նրանք սահմանափակ են, որտեղ միաձուլման վատագույն դեպքը միաժամանակ է ընթանում տեսակավորման լավագույն դեպքի հետ։ Շարժման պայմաններում միաձուլման վատագույն դեպքի բաղադրությունը՝ O(n lg n) – ը նույնն է, ինչ որ արագ տեսակավորման դեպքում, և լավագույն դեպքը խլում է կեսը, ինչպես շատ կրկնություններ վատագույն դեպքում։ Միաձուլման ռեկուրսիվ կատարումը ստիպում է 2n- 1 մեթոդը վատագույն դեպքում համեմատել արագ տեսակավորման n – ի հետ, չնայած միաձուլումն ունի մոտավորապես 2 անգամ ավել ռեկուրսիվ ավելցուկ, քան արագ տեսակավորումը։ Այնուամենայնիվ, միաձուլման կրկնվող ոչ ռեկուրսիվ կատարումները, խուսափելով ավելցուկ կոչվող մեթոդից, դժվար չէ կոդավորել։ Միաձուլման ամենատարածված կատարումը չի տեսակավորվում տեղում, դրա համար մուտքի հիշողության ծավալը պետք է առանձնացված լինի տեսակավորված ելքի տեսակավորման համար։

Միաձուլումը, ինչպես նշված է, նույնպես ունի հաճախակի վերահսկողություն, պրակտիկորեն կարևոր է լավագույն դեպքի հատկությունը։ Եթե մուտքն արդեն տեսակավորված է, դրա բարդությունն ընկնում է մինչև O(n)։ Մասնավորապես, n-1 համեմատությունները և 0 շարժումները ներկայացված են, որը նույնն է, ինչ հասարակ անցումը մուտքով, ստուգելով, արդյոք այն վերատեսակավորված է։ 
Տեղում տեսակավորումը հնարավոր է (օգտագործելով էջերը զանդվածների փոխարեն), բայց շատ դժվար և պրակտիկայում առաջարկում է փոքր ներկայացման ձեռքբերված նույնիսկ եթե ալգորիթմը տևում է O(n log n) ժամ։ Տվյալ դեպքերում ալգորիթմները կուտակված տեսակավորման նման հաճախ առաջարկում են համեմատական արագություն, և պակաս կոմպլեքս են։ Պայմանականորեն, չնայած ստանդարտ միաձուլման, տեղում կատարվող միաձուլումը ստաբիլ տեսակի չէ։ Հղված էջերի դեպքում ալգորիթմը չի օգտագործում ավել տարածք, քան արդեն էջերի ներկայացման ժամանակ օգտագործված տարածքը, բայց O(log(k)) օգտագործվում է ռեկուրսիվ հետքի ժամանակ։

Միաձուլումն ավելի արդյունավետ է, քան արագ տեսակավորումը որոշ էջերի համար, եթե տեսակավորվող ամսաթիվը կարող է լինել միայն արդյունավետորեն թույլատրված հերթականությամբ և հայտնի Lisp –ի նման լեզուներում, որտեղ հերթականությամբ թույլատրված թվային ստրուկտուրաները շատ նման են։ Ի տարբերություն արագ տեսակավորման որոշ( արդյունավետ ) կատարումների, միաձուլումը ստաբիլ տեսակավորում է այնքան ժամանակ, քանի դեռ միաձուլման օպերացիան ճիշտ է կատարված։ Միաձուլումը նույնպես ունի որոշ պայմաններ։ Դրանցից մեկը նրա 2n դիրքի օգտագործումն է, պայմանական n դիրքերն անհրաժեշտ են, քանի որ հնարավոր չէ տեղում տրամաբանորեն կապել 2 տեսակավորված խմբեր։ Բայց չնայած այս տարածքի օգտագործման ալգորիթմը դեռևս շատ աշխատանք է անում։ m – ի պարունակությունը առաջին անգամ պատճենվել է միաձուլման յուրաքանչյուր փուլի արդյունքային էջի ձախ կամ աջ մասում։ Այդ պատճենման ալտերնատիվն ինֆորմացիայի նոր դաշտը բանալու հետ ասոցիացնելն է (m – ի էլեմենտները կոչվում են բանալիներ)։ Այս դաշտը կօգտագործվի բանալիները և յուրաքանչյուր կապված ինֆորմացիա իրար հետ կապելու տեսակավորված էջում (բանալին և նրա վերաբերյալ ինֆորմացիան կոչվում է գրառում)։ Այնուհետև տեսակավորված էջերի միաձուլումը կատարվում է կապի արժեքները փոփոխելով։ Ոչ մի գրառում կարիք չկա տեղաշարժել։ Դաշտը, որը պարունակում է միայն կապ, հիմնականում փոքր կլինի լիարժեք գրառումից, հետևաբար քիչ տարածք կօգտագործվի։ Տարածքի n/2- ից մեկ այլ ալտերնատիվ է դիտարկել աջը և ձախը որպես միասնական ստրուկտուրա, պատճենել m -ի միայն ձախ մասը ժամանակավոր տարածքում և ուղեկցել միաձուլման սահմանված կարգը, տեղադրել միաձուլված արտադրանքը m -ի մեջ։ Ավելի լավ է առանձնացնել ժամանակավոր տարածքը միաձուլված սահմանված կարգից դուրս այնպես, որ անհրաժեշտ լինի միայն մեկ առանձնացում։ Չափից ավելի պատճենումը, որը պահպանվել է նախորդ պարագրաֆում, նույնպես գործում է, քանի դեռ տողերի վերջին զույգը՝ մինչ ետադարձ արդյունքի պնդումը, չի դարձել գերծավալուն։

Օգտագործումը չափերիզների կրիչների հետ 

Արտաքին միաձուլումը պրակտիկ է ժապավենի շարժակներն օգտագործել որպես մուտքային և ելքային սարքեր։ Այն ունի փոքր հիշողության ծավալ և դա կախված չէ գրառումների թվից։

Այդ նույն պատճառով այն օգտակար է սկավառակի վրա ինֆորմացիայի տեսակավորման համար, որը շատ մեծ է հիմնական հիշողությունում պահելու համար։ Եթե ունենք 4 ժապավենի շարժիչներ, դրանք աշխատում են հետևյալ կերպ՝ 
1. Կիսել հատվածը և դնել 2 ժապավենների մեջ։
2. Միավորել 2 ժապավենների գրառումների յուրահատուկ մասերը, գրել 2 առանձին գրառում արտադրվող 2 ժապավենների համար։
3. Միավորել 2 արտադրված ժապավենների գրառումները և գրել դրանք օրիգինալ 2 մուտքային ժապավեններին։ 
4. Կրկնել, մինչև ստանաք մեկ քայլ, որը կպարունակի ամբողջ ժամանակահատվածը, կտարբերակի, որ log n-ն անցել է, որտեղ n-ը գրառումների թիվն է։

Ժապավենների վրա արդեն տեսակավորված ժամանակահատվածի համար տարածված է բնական միաձուլում  տարբերակը։ 
Վատագույն դեպքում այն արտացոլում է այն, ինչ ներսում է, այն միավորում է առանձնահատուկ գրառումները 2 գրառումների ցուցակի մեջ, այնուհետև 2-ը՝ 4- ի մեջ, և այլն։ Լավագույն դեպքում այն միավորում է լայնածավալ, արդեն տեսակավորված ցուցակներն ավելի ծավալուն ցուցակների մեջ, հուսալիորեն ավարտելով ավելի քիչ ժամանակում, քան log n- ն է անցնում։ 
Պարզագույն pseudocode ձևում բնական միաձուլման տեսակավորման ալգորիթմն ունի հետևյալ տեսքը՝

 # Original data is on the input tape; the other tapes are blank
 function merge_sort(input_tape, output_tape, scratch_tape_C, scratch_tape_D)
 while any records remain on the input_tape
 while any records remain on the input_tape
 merge( input_tape, output_tape, scratch_tape_C)
 merge( input_tape, output_tape, scratch_tape_D)
 while any records remain on C or D
 merge( scratch_tape_C, scratch_tape_D, output_tape)
 merge( scratch_tape_C, scratch_tape_D, input_tape)

 # take the next sorted run from the input tapes, and merge into the single given output_tape.
 # tapes are scanned linearly.
 # tape[next] gives the record currently under the read head of that tape.
 # tape[current] gives the record previously under the read head of that tape.
 # (Generally both tape[current] and tape[previous] are buffered in RAM ...)
 function merge(left[], right[], output_tape[])
 do
 if left[current] ≤ right[current]
 append left[current] to output_tape
 read next record from left tape
 else
 append right[current] to output_tape
 read next record from right tape
 while left[current] < left[next] and right[current] < right[next]
 if left[current] < left[next]
 append current_left_record to output_tape
 if right[current] < right[next]
 append current_right_record to output_tape
 return

Օպտիմալացվող միաձուլման տեսակավորում

Ժամանակակից համակարգիչներում առնչության լոկալացումը կարող է հսկայական կարևորություն ունենալ թեթև արդյունաբերության մեջ, քանի որ օգտագործվում են հիերարխիկ հիշողություններ։ Միաձուլման ալգորիթմի Cache տարբերակը, որի գործողությունները հատուկ ընտրված են էջերի շարժման մինիմիզացման համար մեքենայի Cache հիշողության ներսում և դրսում, առաջարկված են։ Օրինակ tiled միաձուլման ալգորիթմը դադարեցրեց ենթազանգվածների մասնակցությունը, երբ S չափի ենթազանգվածները նվաճված են, որտեղ S- ը ժամանակահատվածի թիվն է, որը զբաղեցնում է CPU- ի cache- ը։ Այս ենթազանգվածներից յուրաքանչյուրն ընտրված է տեղում տեսակավորմամբ, խափանել հիշողության փոխանակումները և նորմալ միաձուլումն ավարտվում է ստանդարտ ռեկուրսիվ ձևով։ Այս ալգորիթմն ունեցել է ավելի լավ ազդեցություն մեքենաների վրա։ Քրոնռոդն առաջարկել է միաձուլման ալտերնատիվ միջոց, որն օգտագործում է միայն իր համար նախատեսված տարածքը։

Զուգահեռ գործընթաց
 Միաձուլումը լավ համընկնում է բաժանիր և տիրիր մեթոդի հետ։ Զուգահեռ կատարումը ցույց է տրված pseudocode- ում։ Այս ալգորիթմ օգտագործվում է զուգահեռ միաձուլման ալգորիթմը զանգվածի ռեկուրսիվ բաժանումը ոչ միայն զուգորդման, այլև միաձուլման գործընթացում։ insertion sort,

Համեմատումն այլ տեսակավորման ալգորիթմների հետ 

Չնայած կուտակված տեսակավորումն ունի միևնույն ժամանակի ծախսը, ինչ միաձուլումը, այն ծախսում է միայն Θ(1) օժանդակ տարածք միաձուլման Θ(n)- ի փոխարեն, և հաճախ ավելի արագ է պրակտիկ կիրառման ժամանակ։ Տիպիկ ժամանակակից կառույցներում արդյունավետ արագ տեսակավորման գործընթացը հիմնականում չեն ներկայացնում միաձուլումը RAM – ի վրա հիմնված զանգվածների տեսակավորման համար։ Մյուս կողմից միաձուլումը ստաբիլ տեսակ է և ավելի արդյունավետ է։ Միաձուլումը հաճախ լավագույն տարբերակն է կապված էջը տեսակավորելու համար։heapsort. quicksortlinked list։

Utility- ն օնլայն տեսակավորման մեջ 
Միաձուլման գործընթացն օգտակար է online տեսակավորման համար, որտեղ էջը տեսակավորելու համար սկզբում ստանում է կտոր ժամանակին, ամբողջի փոխարեն։ Այս ապլիկացիայում մենք տեսակավորում ենք յուրաքանչյուր նոր տեսակավորման ալգորիթմների օգտագործումից ստացված կտոր, և միացնում այն տեսակավորված էջին՝ օգտագործելով միացման գործընթացը։ algorithm|online.

Նշումներ

Կարծիքներ 

. Also Practical In-Place Mergesort. Also

Արտաքին կապեր 

 Merge sort in 20 languages 
 Animated Sorting Algorithms: Merge Sort – graphical demonstration and discussion of array-based merge sort
 Merge sort applet  with level order recursive calls to help improve algorithm analysis
 Dictionary of Algorithms and Data Structures: Merge sort
 Implementation of merge sort in various languages on Rosetta Code
 Literate implementations of merge sort in various languages  on LiteratePrograms
 A colored graphical Java applet  which allows experimentation with initial state and shows statistics
 Simon Tatham's explanation and code for a merge sort
 MergeSort tutorial and Java code for beginners 
 Merge sort Fortran routines
 Merge Sort - Wolfram MathWorld

Տեսակավորման ալգորիթմներ