Դիտել Միաձուլման տեսակավորում էջի վիքիկոդը

{{Տեղեկաքարտ Ալգորիթմ}}
'''Միաձուլման տեսակավորում''' ''[[O]]''(''n'' log ''n''), համեմատման վրա հիմնված տեսակավորման ալգորիթմ է։ Կատարման մեծ մասն արտադրում է ստաբիլ տեսակավորում, որը նշանակում է, որ կատարումը պաշտպանում է մուտքի հրամանը տեսակավորված ելքի հավասար էլեմենտներից։ Դա անջատ և նվաճված ալգորիթմ է։ Միաձուլումը հայտնաբերվել է 1945 թ.-ին Ջոն վոն Նյումանի կողմից<ref>{{Harvtxt|Knuth|1998|p=158}}</ref>
[[Միաձուլման մանրամասն նկարագրությունը և քննությունն առաջացել է Գոլդստինի և Նյումանի աշխատություններում 1948 – ին։|Goldstine]]<ref>{{Cite journal |year=1997 |title=A meticulous analysis of mergesort programs |authors=Jyrki Katajainen and Jesper Larsson TrՊff}}</ref>:

== Ալգորիթմ ==
Միաձուլման տեսակավորման օրինակ։ Առաջին հերթին բաժանել էջը փոքրագույն մասնիկների, ապա համեմատել յուրաքանչյուր մասնիկ հարակից էջի հետ՝ տեսակավորելու և միավորելու երկու հարակից էջերը։ Արդյունքում բոլոր մասնիկները տեսակավորվում և միավորվում են իրար։ Միաձուլումը տեղի է ունենում հետևյալ կերպ՝
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 կեսերը վերադարձվում են, դրանք պետք է տեսակավորվեն։ Դրանք այժմ կարող են միաձուլվել միմյանց հետ՝ կազմելով տեսակավորված զանգված։ <math>An-1_0</math> to <math>A_{n-1}</math>.

[[Հասարակ 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

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

 '''function''' merge(left, right)
 '''var''' ''list'' result
 '''while''' length(left) &gt; 0 '''or''' length(right) &gt; 0
 '''if''' length(left) &gt; 0 '''and''' length(right) &gt; 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) &gt; 0
 append first(left) to result
 left = rest(left)
 '''else if''' length(right) &gt; 0
 append first(right) to result
 right = rest(right)
 '''end while'''
 '''return''' result

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

Տեսակավորման ''n'' միաձուլվող օբյեկտներն ունեն O(n log n ) – ի ներկայացման միջին և վատագույն դեպքեր։ Եթե ''n'' լայնության էջի միաձուլման ժամանակը ''T''( ''n'') է, ''T''(''n'') = 2''T''(''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) – ը նույնն է, ինչ որ արագ տեսակավորման դեպքում, և լավագույն դեպքը խլում է կեսը, ինչպես շատ կրկնություններ վատագույն դեպքում։ Միաձուլման ռեկուրսիվ կատարումը ստիպում է 2''n''- 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- ը։ Այս ենթազանգվածներից յուրաքանչյուրն ընտրված է տեղում տեսակավորմամբ, խափանել հիշողության փոխանակումները և նորմալ միաձուլումն ավարտվում է ստանդարտ ռեկուրսիվ ձևով։ Այս ալգորիթմն ունեցել է ավելի լավ ազդեցություն մեքենաների վրա։ Քրոնռոդն առաջարկել է միաձուլման ալտերնատիվ միջոց, որն օգտագործում է միայն իր համար նախատեսված տարածքը։

== Զուգահեռ գործընթաց ==
<ref>{{Citation |last1=Cormen |first1=Thomas |title=Introduction to Algorithms=Third Edition, MIT Press and McGraw-Hill, 2009 |page=803 |last2=Leiserson |first2=Charles |last3=Rivest |first3=Ronald |last4=Stein |first4=Clifford}}.</ref> Միաձուլումը լավ համընկնում է բաժանիր և տիրիր մեթոդի հետ։ Զուգահեռ կատարումը ցույց է տրված pseudocode- ում։ Այս ալգորիթմ օգտագործվում է զուգահեռ միաձուլման ալգորիթմը զանգվածի ռեկուրսիվ բաժանումը ոչ միայն զուգորդման, այլև միաձուլման գործընթացում։ [[insertion sort]]<ref>[http://drdobbs.com/high-performance-computing/229400239 V. J. Duvanenko, "Parallel Merge Sort", Dr. Dobb's Journal, March 2011]</ref>,

== Համեմատումն այլ տեսակավորման ալգորիթմների հետ ==
Չնայած կուտակված տեսակավորումն ունի միևնույն ժամանակի ծախսը, ինչ միաձուլումը, այն ծախսում է միայն Θ(1) օժանդակ տարածք միաձուլման Θ(''n'')- ի փոխարեն, և հաճախ ավելի արագ է պրակտիկ կիրառման ժամանակ։ Տիպիկ ժամանակակից կառույցներում արդյունավետ արագ տեսակավորման գործընթացը հիմնականում չեն ներկայացնում միաձուլումը RAM – ի վրա հիմնված զանգվածների տեսակավորման համար։ Մյուս կողմից միաձուլումը ստաբիլ տեսակ է և ավելի արդյունավետ է։ Միաձուլումը հաճախ լավագույն տարբերակն է կապված էջը տեսակավորելու համար։heapsort. [[quicksort]]{{Citation needed|date=January 2011}}[[linked list]]։

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

== Նշումներ ==
{{Ծանցանկ}}

== Կարծիքներ ==
*{{Cite news |last1=Katajainen |first1=Jyrki |last2=Pasanen |first2=Tomi |last3=Teuhola |first3=Jukka |year=1996 |title=Practical in-place mergesort |url=http://www.diku.dk/hjemmesider/ansatte/jyrki/Paper/mergesort_NJC.ps |url-status=dead |archive-url=https://web.archive.org/web/20110807033704/http://www.diku.dk/hjemmesider/ansatte/jyrki/Paper/mergesort_NJC.ps |archive-date=2011 թ․ օգոստոսի 7 |accessdate=2009 թ․ ապրիլի 4 |periodical=Nordic Journal of Computing |pages=27–40 |volume=3 |issn=1236-6064 |postscript=<!--None-->}}. Also [http://citeseer.ist.psu.edu/katajainen96practical.html Practical In-Place Mergesort]. Also [http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.22.8523]
* {{Cite book |last=Knuth |first=Donald |title=Sorting and Searching |publisher=Addison-Wesley |year=1998 |isbn=0-201-89685-0 |edition=2nd |series=[[The Art of Computer Programming]] |volume=3 |pages=158–168 |chapter=Section 5.2.4: Sorting by Merging |authorlink=Donald Knuth}}
*{{Cite news |last=Kronrod |first=M. A. |year=1969 |title=Optimal ordering algorithm without operational field |periodical=Soviet Mathematics - Doklady |pages=744 |volume=10 |postscript=<!--None-->}}
*{{Cite journal |last=LaMarca |first=A. |last2=Ladner |first2=R. E. |year=1997 |title=The influence of caches on the performance of sorting |journal=Proc. 8th Ann. ACM-SIAM Symp. on Discrete Algorithms (SODA97) |pages=370&ndash;379 |postscript=<!--None-->}}
* {{Cite web |author=Sun Microsystems, Inc. |title=Arrays API |url=http://java.sun.com/javase/6/docs/api/java/util/Arrays.html |accessdate=2007 թ․ նոյեմբերի 19–ին}}
* {{Cite web |author=Sun Microsystems, Inc. |title=java.util.Arrays.java |url=https://openjdk.dev.java.net/source/browse/openjdk/jdk/trunk/jdk/src/share/classes/java/util/Arrays.java?view=markup |accessdate=2007 թ․ նոյեմբերի 19–ին}}{{Չաշխատող արտաքին հղում|bot=InternetArchiveBot }}

== Արտաքին կապեր ==
{{wikibooks|Algorithm implementation|Sorting/Merge_sort|Merge sort}}
* [http://www.codecodex.com/wiki/Merge_sort Merge sort in 20 languages] {{Webarchive|url=https://web.archive.org/web/20110318124652/http://www.codecodex.com/wiki/Merge_sort |date=2011-03-18 }}
* [https://www.toptal.com/developers/sorting-algorithms Animated Sorting Algorithms: Merge Sort] – graphical demonstration and discussion of array-based merge sort
* [http://www.atkinson.yorku.ca/~sychen/research/sorting/sortingHome.html Merge sort applet] {{Webarchive|url=https://web.archive.org/web/20090228175036/http://www.atkinson.yorku.ca/~sychen/research/sorting/sortingHome.html |date=2009-02-28 }} with [[Tree traversal|level order]] recursive calls to help improve algorithm analysis
* [http://www.nist.gov/dads/HTML/mergesort.html Dictionary of Algorithms and Data Structures: Merge sort]
* [http://www.rosettacode.org/wiki/Merge_sort Implementation of merge sort in various languages] on [[Rosetta Code]]
* [http://en.literateprograms.org/Category:Merge_sort Literate implementations of merge sort in various languages] {{Webarchive|url=https://web.archive.org/web/20090618083928/http://en.literateprograms.org/Category:Merge_sort |date=2009-06-18 }} on LiteratePrograms
* [http://coderaptors.com/?MergeSort A colored graphical Java applet] {{Webarchive|url=https://web.archive.org/web/20110708174304/http://coderaptors.com/?MergeSort |date=2011-07-08 }} which allows experimentation with initial state and shows statistics
* [http://www.chiark.greenend.org.uk/~sgtatham/algorithms/listsort.html Simon Tatham's explanation and code for a merge sort]
* [http://www.mycstutorials.com/articles/sorting/mergesort MergeSort tutorial and Java code for beginners] {{Webarchive|url=https://web.archive.org/web/20110714142249/http://www.mycstutorials.com/articles/sorting/mergesort |date=2011-07-14 }}
* [http://www.fortran-2000.com/rank/ Merge sort Fortran routines]
* [http://mathworld.wolfram.com/MergeSort.html Merge Sort - Wolfram MathWorld]
{{Տեսակավորում}}

[[Կատեգորիա:Տեսակավորման ալգորիթմներ]]