การเรียงลำดับแบบผสาน

ตัวอย่างของการเรียงลำดับแบบผสาน (Merge Sort) ขั้นแรก แบ่งรายการออกเป็นหน่วยที่เล็กที่สุด (1 องค์ประกอบ) จากนั้นเปรียบเทียบแต่ละองค์ประกอบกับรายการที่อยู่ติดกันเพื่อเรียงลำดับและผสานรายการที่อยู่ติดกันทั้งสองรายการ สุดท้าย องค์ประกอบทั้งหมดจะถูกเรียงลำดับและผสานเข้าด้วยกัน
ระดับ	อัลกอริทึมการเรียงลำดับ
โครงสร้างข้อมูล	อาร์เรย์
ประสิทธิภาพในกรณีที่เลวร้ายที่สุด	${\displaystyle O(n\log n)}$
ประสิทธิภาพในกรณีที่ดีที่สุด	${\displaystyle \โอเมก้า (n\log n)}$รูปแบบ ทั่วไป ตามธรรมชาติ${\displaystyle \Omega (n)}$
ประสิทธิภาพโดยเฉลี่ย	${\displaystyle \Theta (n\log n)}$
ความซับซ้อนของพื้นที่ในกรณีที่เลวร้ายที่สุด	${\displaystyle O(n)}$ทั้งหมดพร้อมตัวช่วยตัวช่วยพร้อมรายการเชื่อมโยง[ 1 ]${\displaystyle O(n)}$${\displaystyle O(1)}$

อัลกอริทึมการเรียงลำดับแบบผสาน (มักสะกดว่าmergesortหรือmerge-sort ^{[ 2 ]} ) เป็นอัลกอริทึมการเรียงลำดับแบบเปรียบเทียบ ที่มีประสิทธิภาพและใช้งาน ได้ ทั่วไป การใช้งานอัลกอริ ทึมการเรียงลำดับแบบผสานส่วนใหญ่มีเสถียรภาพซึ่งหมายความว่าลำดับสัมพัทธ์ขององค์ประกอบที่เท่ากันจะเหมือนกันระหว่างอินพุตและเอาต์พุต อัลกอริทึมการเรียงลำดับแบบผสานเป็นอัลกอริทึมแบบแบ่งและพิชิตที่คิดค้นโดยJohn von Neumannในปี 1945 ^{[ 3 ]}คำอธิบายและการวิเคราะห์โดยละเอียดของอัลกอริทึมการเรียงลำดับแบบผสานจากล่างขึ้นบนปรากฏในรายงานของGoldstineและ von Neumann ตั้งแต่ปี 1948 ^{[ 4 ]}

โดยหลักการแล้ว การเรียงลำดับแบบผสาน (merge sort) ทำงานดังนี้:

1. แบ่งรายการที่ไม่เรียงลำดับออกเป็นnรายการย่อย โดยแต่ละรายการย่อยจะมีองค์ประกอบเพียงหนึ่งเดียว (รายการที่มีองค์ประกอบเพียงหนึ่งเดียวถือว่าเรียงลำดับแล้ว)
2. ทำการผสาน รายการย่อย ซ้ำๆเพื่อสร้างรายการย่อยที่เรียงลำดับใหม่ จนกว่าจะเหลือรายการย่อยเพียงรายการเดียว ซึ่งจะเป็นรายการที่เรียงลำดับแล้ว

การเรียงลำดับแบบผสาน (Merge sort) มีประสิทธิภาพเนื่องจากสามารถผสานและเรียงลำดับรายการย่อยสองรายการได้ในเวลาเชิงเส้น โดยมีเงื่อนไขว่ารายการย่อยเหล่านั้นได้รับการเรียงลำดับแล้ว

ตัวอย่าง โค้ด คล้ายภาษาซีที่ใช้ดัชนีสำหรับอัลกอริธึมการเรียงลำดับแบบผสานจากบนลงล่าง ซึ่งจะแบ่งรายการออกเป็นรายการย่อย (เรียกว่า " รัน"ในตัวอย่างนี้) ซ้ำๆ จนกว่าขนาดของรายการย่อยจะเป็น 1 จากนั้นจึงผสานรายการย่อยเหล่านั้นเข้าด้วยกันเพื่อสร้างรายการที่เรียงลำดับแล้ว ขั้นตอนการคัดลอกกลับจะถูกหลีกเลี่ยงโดยการสลับทิศทางการผสานในแต่ละระดับของการเรียกซ้ำ (ยกเว้นการคัดลอกครั้งเดียวในตอนเริ่มต้น ซึ่งสามารถหลีกเลี่ยงได้เช่นกัน)

ยกตัวอย่างง่ายๆ ลองพิจารณาอาร์เรย์ที่มีสององค์ประกอบ องค์ประกอบเหล่านั้นจะถูกคัดลอกไปยังbจากนั้นรวมกลับไปยังaหากมีสี่องค์ประกอบ เมื่อถึงระดับการเรียกซ้ำล่างสุด ส่วนที่มีองค์ประกอบเดียวจากaจะถูกรวมเข้ากับ จากbนั้นในระดับการเรียกซ้ำที่สูงขึ้นถัดไป ส่วนที่มีองค์ประกอบสองตัวเหล่านั้นจะถูกรวมเข้ากับaรูปแบบนี้จะดำเนินต่อไปในแต่ละระดับของการเรียกซ้ำ

// คัดลอกส่วนหนึ่งของอาร์เรย์ a ไปยังอาร์เรย์ b (จาก begin ถึง end - 1) void copyArray ( int [] a , int begin , int end , int [] b ) { for ( int k = begin ; k < end ; ++ k ) { b [ k ] = a [ k ] ; } }// รวมสองส่วนที่เรียงลำดับแล้ว (จาก a) เข้าเป็นลำดับเดียวที่เรียงลำดับแล้ว (ใน b) void topDownMerge ( int [] a , int begin , int middle , int end , int [] b ) { int i = begin ; int j = middle ;// รวมลำดับสองชุดเข้าด้วยกันใน b สำหรับ( int k = begin ; k < end ; ++ k ) { ถ้า( i < middle && ( j >= end || a [ i ] <= a [ j ] )) { b [ k ] = a [ i ] ; // นำองค์ประกอบจากลำดับด้านซ้ายi ++ ; } มิฉะนั้น{ b [ k ] = a [ j ] ; // นำองค์ประกอบจากลำดับด้านขวาj ++ ; } } }// แบ่งอาร์เรย์ a ออกเป็นสองส่วนเท่าๆ กัน เรียงลำดับทั้งสองส่วนลงใน b // และรวมส่วนที่เรียงลำดับแล้วกลับเข้าไปใน a void topDownSplitMerge ( int [] a , int begin , int end , int [] b ) { if ( end - begin <= 1 ) { return ; // กรณีพื้นฐาน: ขนาดของลำดับคือ 1 ดังนั้นจึงเรียงลำดับแล้ว} }int middle = ( begin + end ) / 2 ; // หาจุดกึ่งกลางเพื่อแบ่งอาร์เรย์// เรียงลำดับครึ่งซ้ายและขวาแบบเรียกซ้ำลงใน b topDownSplitMerge ( b , begin , middle , a ); topDownSplitMerge ( b , middle , end , a );// รวมครึ่งที่เรียงลำดับแล้วกลับเข้าไปในtopDownMerge ( b , begin , middle , end , a ); }void topDownMergeSort ( int [] a , int [] b , int n ) { // คัดลอกอาร์เรย์ a ทั้งหมดลงใน b ในขั้นต้นcopyArray ( a , 0 , n , b ); // แยกและรวมอาร์เรย์ b เข้ากับ a แบบเรียกซ้ำtopDownSplitMerge ( a , 0 , n , b ); }

การเรียงลำดับอาร์เรย์ทั้งหมดทำได้โดยใช้topDownMergeSort(a, b, a.length )

ตัวอย่างโค้ดที่คล้ายกับภาษา C โดยใช้ดัชนีสำหรับอัลกอริธึมการเรียงลำดับแบบผสานจากล่างขึ้นบน ซึ่งถือว่าลิสต์เป็นอาร์เรย์ของ ลิสต์ย่อย nรายการ (เรียกว่าrunsในตัวอย่างนี้) ที่มีขนาด 1 และผสานลิสต์ย่อยไปมาระหว่างบัฟเฟอร์สองตัวอย่างต่อเนื่อง:

// คัดลอกอาร์เรย์ b ไปยังอาร์เรย์ a void copyArray ( int [] b , int [] a , int n ) { for ( int i = 0 ; i < n ; i ++ ) { a [ i ] = b [ i ] ; } }// รันด้านซ้ายคือ a[left : right-1] // รันด้านขวาคือ a[right : end-1] void bottomUpMerge ( int [] a , int left , int right , int end , int [] b ) { int i = left ; int j = right ;// ในขณะที่มีองค์ประกอบอยู่ในแถวซ้ายหรือขวา... สำหรับ( int k = left ; k < end ; ++ k ) { // ถ้าหัวแถวซ้ายมีอยู่และ <= หัวแถวขวาที่มีอยู่if ( i < right && ( j >= end || a [ i ] <= a [ j ] )) { b [ k ] = a [ i ] ; i = i + 1 ; } else { b [ k ] = a [ j ] ; j = j + 1 ; } } }void bottomUpMergeSort ( int [] a , int [] b , int n ) { // แต่ละลำดับที่มี 1 องค์ประกอบใน a นั้น "เรียงลำดับ" แล้ว// สร้างลำดับที่ยาวขึ้นเรื่อยๆ เป็น 2, 4, 8, 16... จนกว่าอาร์เรย์ทั้งหมดจะถูกเรียงลำดับfor ( int width = 1 ; width < n ; width *= 2 ) { // อาร์เรย์ a เต็มไปด้วยลำดับที่มีความยาว width for ( int i = 0 ; i < n ; i = i + 2 * width ) { // รวมสองชุดข้อมูล: a[i:i+width-1] และ a[i+width:i+2*width-1] ลงใน b[] // หรือคัดลอก a[i:n-1] ไปยัง b[] (ถ้า (i+width >= n)) bottomUpMerge ( a , i , Math.min ( i + width , n ) , Math.min ( i + 2 * width , n ) , b ); } // ตอนนี้อาร์เรย์ b เต็มไปด้วยชุดข้อมูลที่มีความยาว 2 * width // คัดลอกอาร์เรย์ b ไปยังอาร์เรย์ a สำหรับการวนซ้ำครั้งต่อไป // การใช้งานที่มีประสิทธิภาพมากกว่าคือการสลับบทบาทของ a และ b copyArray ( b , a , n ); } }

รหัสเทียมสำหรับอัลกอริธึมการเรียงลำดับแบบผสานจากบนลงล่าง ซึ่งจะแบ่งรายการอินพุตออกเป็นรายการย่อยที่เล็กลงเรื่อยๆ จนกว่ารายการย่อยเหล่านั้นจะเรียงลำดับได้โดยง่าย จากนั้นจึงผสานรายการย่อยเหล่านั้นเข้าด้วยกันในขณะที่ส่งค่ากลับขึ้นไปตามลำดับการเรียก

ฟังก์ชัน merge_sort( list m) คือ // กรณีพื้นฐาน รายการที่มีองค์ประกอบศูนย์หรือหนึ่งรายการจะถูกเรียงลำดับตามนิยามถ้าความยาวของ m ≤ 1 ให้คืนค่า m // กรณีเรียกซ้ำ ขั้นแรก แบ่งรายการออกเป็นรายการย่อยที่มีขนาดเท่ากัน // ซึ่งประกอบด้วยครึ่งแรกและครึ่งหลังของรายการ // สมมติว่ารายการเริ่มต้นที่ดัชนี 0 var left := รายการว่าง var right := รายการว่าง สำหรับแต่ละ x ที่มีดัชนี i ใน m ทำซ้ำถ้า i < (ความยาวของ m)/2 แล้ว เพิ่ม x ไปทางซ้าย อื่น เพิ่ม x ไปทางขวา // เรียงลำดับรายการย่อยทั้งสองรายการแบบเรียกซ้ำ ซ้าย := ผสานเรียงลำดับ (ซ้าย) ขวา := ผสานเรียงลำดับ (ขวา) // จากนั้นรวมรายการย่อยที่เรียงลำดับแล้วเข้าด้วยกัน คืนค่าผสาน (ซ้าย, ขวา) 

ในตัวอย่างนี้ ฟังก์ชัน mergeจะรวมรายการย่อยด้านซ้ายและด้านขวาเข้าด้วยกัน

ฟังก์ชัน merge(left, right) คือvar result := รายการว่างเปล่า ในขณะที่ left ไม่ว่างเปล่าและ right ไม่ว่างเปล่าให้ทำดังนี้ ถ้า first(left) ≤ first(right) แล้ว เพิ่ม first(left) ลงในผลลัพธ์ ซ้าย := ส่วนที่เหลือ (ซ้าย) อื่น เพิ่มผลลัพธ์แรก (ขวา) ลงในผลลัพธ์ ขวา := ส่วนที่เหลือ (ขวา) // ด้านซ้ายหรือด้านขวาอาจมีองค์ประกอบอยู่ ให้ใช้องค์ประกอบเหล่านั้น // (ลูปต่อไปนี้จะทำงานเพียงหนึ่งเดียวเท่านั้น) ในขณะที่ด้านซ้ายไม่ว่างเปล่าทำซ้ำ เพิ่ม first(left) ลงในผลลัพธ์ ซ้าย := ส่วนที่เหลือ (ซ้าย) ในขณะที่สิทธิ์ไม่ว่างเปล่า เพิ่มผลลัพธ์แรก (ขวา) ลงในผลลัพธ์ ขวา := ส่วนที่เหลือ (ขวา) ส่งคืนผลลัพธ์ 

รหัสเทียมสำหรับอัลกอริธึมการเรียงลำดับแบบผสานจากล่างขึ้นบน (bottom-up merge sort) ซึ่งใช้อาร์เรย์ขนาดเล็กคงที่ของตัวอ้างอิงถึงโหนด โดยที่ ` i` array[i]เป็นตัวอ้างอิงถึงรายการที่มีขนาด 2 _ⁱ หรือ`nil` ` node`เป็นตัวอ้างอิงหรือตัวชี้ไปยังโหนดmerge()ฟังก์ชันจะคล้ายกับฟังก์ชันที่แสดงในตัวอย่างการผสานรายการจากบนลงล่าง (top-down merge lists) โดยจะผสานรายการที่เรียงลำดับแล้วสองรายการ และจัดการกับรายการว่าง ในกรณีนี้ ฟังก์ชันmerge()จะใช้`node`เป็นพารามิเตอร์อินพุตและค่าส่งคืน

ฟังก์ชัน merge_sort( node head) คือ // ส่งคืนค่าหากรายการว่างเปล่า ถ้า head = nil ให้คืนค่า nil var node array[32]; เริ่มต้นทั้งหมดเป็น nil var node result var node next var int i ผลลัพธ์ := หัว // รวมโหนดเข้าในอาร์เรย์ ในขณะที่ผลลัพธ์ไม่เท่ากับศูนย์ให้ทำ ซ้ำ ถัดไป := ผลลัพธ์ถัดไป; ผลลัพธ์ถัดไป := nil สำหรับ (i = 0; (i < 32) และ (array[i] ≠ nil); i += 1) ทำ ผลลัพธ์ := ผสาน (อาร์เรย์[i], ผลลัพธ์) array[i] := nil // ห้ามเกินขอบเขตของอาร์เรย์ ถ้า i = 32 แล้ว i -= 1 อาร์เรย์[i] := ผลลัพธ์ ผลลัพธ์ := ถัดไป // รวมอาร์เรย์เข้าเป็นลิสต์เดียว ผลลัพธ์ := nil สำหรับ (i = 0; i < 32; i += 1) ทำ ผลลัพธ์ := ผสาน (อาร์เรย์[i], ผลลัพธ์) ส่งคืนผลลัพธ์ 

รหัสเทียมที่คล้ายกับ Haskellซึ่งแสดงให้เห็นว่าสามารถใช้งานการเรียงลำดับแบบผสาน (merge sort) ในภาษาดังกล่าวได้อย่างไร โดยใช้โครงสร้างและแนวคิดจาก การ เขียน โปรแกรมเชิงฟังก์ชัน

mergeSort :: Ord a => [ a ] ​​-> [ a ] ​​mergeSort [] = [] mergeSort [ x ] = [ x ] mergeSort xs = merge ( mergeSort l , mergeSort r ) where ( l , r ) = splitAt ( length xs ` div ` 2 ) xsmerge :: Ord a => ([ a ], [ a ]) -> [ a ] ​​merge ( [] , xs ) = xs merge ( xs , [] ) = xs merge ( x : xs , y : ys ) | x <= y = x : merge ( xs , y : ys ) | otherwise = y : merge ( x : xs , ys )

ในการเรียงลำดับ วัตถุ nชิ้น การเรียงลำดับแบบผสานมี ประสิทธิภาพ โดยเฉลี่ยและกรณีที่เลวร้ายที่สุดคือO ( n  log  n ) การเปรียบเทียบ หากเวลาในการทำงาน (จำนวนการเปรียบเทียบ) ของการเรียงลำดับแบบผสานสำหรับรายการที่มีความยาวnคือT ( n ) แล้วความสัมพันธ์เวียนเกิดT ( n ) = 2 T ( n /2) + nจะเป็นไปตามคำจำกัดความของอัลกอริทึม (ใช้อัลกอริทึมกับรายการสองรายการที่มีขนาดครึ่งหนึ่งของรายการเดิม และเพิ่ม ขั้นตอน nที่ใช้ในการผสานรายการสองรายการที่ได้) ^{[ 5 ]}รูปแบบปิดเป็นไปตาม ทฤษฎีบทหลักสำหรับความสัมพันธ์เวียน เกิด แบบแบ่งและพิชิต

จำนวนการเปรียบเทียบที่ทำโดย merge sort ในกรณีที่เลวร้ายที่สุดจะกำหนดโดยตัวเลขการเรียงลำดับตัวเลขเหล่านี้เท่ากับหรือน้อยกว่าเล็กน้อย ( n  ⌈ lg  n ⌉ − 2 ^{⌈lg  n ⌉} + 1) ซึ่งอยู่ระหว่าง ( n  lg  n − n + 1) และ ( n  lg  n + n + O(lg  n )) ^{[ 6 ]}กรณีที่ดีที่สุดของ merge sort ใช้จำนวนรอบประมาณครึ่งหนึ่งของกรณีที่เลวร้ายที่สุด^{[ 7 ]}

สำหรับค่าn ขนาดใหญ่ และรายการข้อมูลป้อนเข้าที่เรียงลำดับแบบสุ่ม จำนวนการเปรียบเทียบโดยเฉลี่ยของ merge sort จะเข้าใกล้ค่าα · nน้อยกว่ากรณีที่เลวร้ายที่สุด โดยที่${\displaystyle \alpha =-1+\sum _{k=0}^{\infty }{\frac {1}{2^{k}+1}}\approx 0.2645.}$

ใน กรณี ที่เลวร้ายที่สุดการเรียงลำดับแบบผสานจะใช้การเปรียบเทียบน้อยกว่าการเรียงลำดับแบบเร็ว ประมาณ 39% ใน กรณี เฉลี่ยและในแง่ของการเคลื่อนย้าย ความซับซ้อนในกรณีที่เลวร้ายที่สุดของการเรียงลำดับแบบผสานคือO ( n  log  n ) ซึ่งมีความซับซ้อนเท่ากับกรณีที่ดีที่สุดของการเรียงลำดับแบบเร็ว^{[ 7 ]}

อัลกอริทึมการเรียงลำดับแบบผสาน (Merge sort) มีประสิทธิภาพมากกว่าการเรียงลำดับแบบเร็ว (Quick sort) สำหรับลิสต์บางประเภท หากข้อมูลที่จะเรียงลำดับสามารถเข้าถึงได้อย่างมีประสิทธิภาพเฉพาะในลำดับเท่านั้น จึงเป็นที่นิยมในภาษาโปรแกรม เช่นLispซึ่งโครงสร้างข้อมูลที่เข้าถึงในลำดับนั้นพบได้ทั่วไป แตกต่างจากวิธีการใช้งาน quicksort ที่มีประสิทธิภาพบางวิธี อัลกอริทึมการเรียงลำดับแบบผสานเป็นการเรียงลำดับแบบเสถียร (Stable sort)

การใช้งาน Merge sort ที่พบได้บ่อยที่สุดจะไม่เรียงลำดับในตำแหน่งเดิม^{[ 8 ]}ดังนั้น ขนาดหน่วยความจำของข้อมูลนำเข้าจะต้องถูกจัดสรรไว้สำหรับการจัดเก็บผลลัพธ์ที่เรียงลำดับแล้ว (ดูด้านล่างสำหรับรูปแบบต่างๆ ที่ต้องการพื้นที่เพิ่มเติมเพียงn /2)

การเรียงลำดับแบบผสานตามธรรมชาติคล้ายกับการเรียงลำดับแบบผสานจากล่างขึ้นบน ยกเว้นว่าลำดับ ที่เกิดขึ้นตามธรรมชาติ (ลำดับที่เรียงลำดับแล้ว) ในข้อมูลนำเข้าจะถูกนำมาใช้ประโยชน์ ทั้งลำดับแบบโมโนโทนิกและไบโทนิก (สลับขึ้น/ลง) สามารถนำมาใช้ประโยชน์ได้ โดยรายการ (หรือเทียบเท่ากับเทปหรือไฟล์) เป็นโครงสร้างข้อมูลที่สะดวก (ใช้เป็นคิว FIFOหรือสแต็ก LIFO ) ^{[ 9 ]}ในการเรียงลำดับแบบผสานจากล่างขึ้นบน จุดเริ่มต้นจะถือว่าแต่ละลำดับมีความยาวหนึ่งรายการ ในทางปฏิบัติ ข้อมูลนำเข้าแบบสุ่มจะมีลำดับสั้นๆ จำนวนมากที่บังเอิญเรียงลำดับแล้ว ในกรณีทั่วไป การเรียงลำดับแบบผสานตามธรรมชาติอาจไม่จำเป็นต้องผ่านหลายรอบเนื่องจากมีลำดับที่จะผสานน้อยกว่า ในกรณีที่ดีที่สุด ข้อมูลนำเข้าจะเรียงลำดับแล้ว (เช่น เป็นลำดับเดียว) ดังนั้นการเรียงลำดับแบบผสานตามธรรมชาติจึงต้องผ่านข้อมูลเพียงรอบเดียว ในหลายกรณีในทางปฏิบัติ ลำดับตามธรรมชาติที่ยาวจะมีอยู่ และด้วยเหตุนี้ การเรียงลำดับแบบผสานตามธรรมชาติจึงถูกนำมาใช้ประโยชน์เป็นส่วนประกอบหลักของTimsortตัวอย่าง:

เริ่ม : 3 4 2 1 7 5 8 9 0 6 เลือกการวิ่ง : (3 4)(2)(1 7)(5 8 9)(0 6) รวม : (2 3 4)(1 5 7 8 9)(0 6) รวม : (1 2 3 4 5 7 8 9)(0 6) ผสาน : (0 1 2 3 4 5 6 7 8 9) 

ตามหลักการแล้ว การเรียงลำดับแบบผสานธรรมชาติ (Natural Merge Sort) กล่าวได้ว่ามี ประสิทธิภาพสูงสุด ตามจำนวนรัน (Runs -optimal) โดยที่คือจำนวนรันในลบด้วยหนึ่ง ${\displaystyle {\mattt {รัน}}(L)}$${\displaystyle L}$

การเรียงลำดับแบบเลือกแทนที่ในทัวร์นาเมนต์ใช้เพื่อรวบรวมผลลัพธ์เริ่มต้นสำหรับอัลกอริทึมการเรียงลำดับภายนอก

แทนที่จะรวมบล็อกสองบล็อกในแต่ละครั้ง การรวมแบบปิงปองจะรวมบล็อกสี่บล็อกในแต่ละครั้ง บล็อกที่เรียงลำดับแล้วสี่บล็อกจะถูกรวมเข้าด้วยกันพร้อมกันไปยังพื้นที่เสริมเป็นบล็อกที่เรียงลำดับแล้วสองบล็อก จากนั้นบล็อกที่เรียงลำดับแล้วสองบล็อกจะถูกรวมกลับไปยังหน่วยความจำหลัก การทำเช่นนี้จะละเว้นการดำเนินการคัดลอกและลดจำนวนการเคลื่อนย้ายทั้งหมดลงครึ่งหนึ่ง การใช้งานแบบรวมสี่บล็อกพร้อมกันในโดเมนสาธารณะในยุคแรกๆ คือ WikiSort ในปี 2014 วิธีนี้ได้รับการอธิบายในภายหลังในปีเดียวกันว่าเป็นการปรับปรุงประสิทธิภาพสำหรับการเรียงลำดับแบบอดทนและตั้งชื่อว่าการรวมแบบปิงปอง^{[ 10 ] [ 11 ]} Quadsort ได้นำวิธีการนี้ไปใช้ในปี 2020 และตั้งชื่อว่าการรวมแบบควอด^{[ 12 ]}

ข้อเสียอย่างหนึ่งของการเรียงลำดับแบบผสาน (merge sort) เมื่อนำไปใช้กับอาร์เรย์ คือ ความต้องการหน่วยความจำในการทำงานแบบ O ( n )มีการเสนอ วิธีการหลายวิธีเพื่อลดหน่วยความจำหรือทำให้การเรียงลำดับแบบผสานทำงานแบบin-place ได้อย่างสมบูรณ์:

• Kronrod (1969)เสนอวิธีการเรียงลำดับแบบผสาน (merge sort) เวอร์ชันทางเลือกที่ใช้พื้นที่เพิ่มเติมคงที่
• Katajainen และคณะนำเสนออัลกอริทึมที่ต้องการหน่วยความจำในการทำงานคงที่: พื้นที่จัดเก็บเพียงพอสำหรับเก็บองค์ประกอบหนึ่งของอาร์เรย์อินพุต และพื้นที่เพิ่มเติมสำหรับเก็บตัวชี้O (1)ในอาร์เรย์อินพุต พวกเขาบรรลุ ขอบเขตเวลา O ( n log n )ด้วยค่าคงที่ขนาดเล็ก แต่อัลกอริทึมของพวกเขาไม่เสถียร^{[ 13 ]}
• มีความพยายามหลายครั้งในการสร้าง อัลกอริทึม การผสานแบบ in-placeที่สามารถรวมเข้ากับการเรียงลำดับแบบผสานมาตรฐาน (แบบบนลงล่างหรือแบบล่างขึ้นบน) เพื่อสร้างการเรียงลำดับแบบผสานแบบ in-place ในกรณีนี้ แนวคิดของ "in-place" สามารถผ่อนคลายให้หมายถึง "การใช้พื้นที่สแต็กแบบลอการิทึม" เนื่องจากอัลกอริทึมการผสานมาตรฐานต้องการพื้นที่จำนวนนั้นสำหรับการใช้งานสแต็กของตัวเอง Geffert และคณะ ได้แสดงให้เห็น ว่าการผสานแบบ in-place ที่เสถียรนั้นเป็นไปได้ใน เวลา O ( n log n )โดยใช้พื้นที่ชั่วคราวคงที่ แต่ขั้นตอนวิธีของพวกเขานั้นซับซ้อนและมีปัจจัยคงที่สูง: การผสานอาร์เรย์ที่มีความยาวnและmอาจใช้การเคลื่อนย้าย5n + 12m + o ( m ) ครั้ง ^{[ 14 ]} ปัจจัยคงที่สูงและขั้นตอน วิธี in-place ที่ซับซ้อนนี้ได้รับการทำให้ง่ายขึ้นและเข้าใจง่ายขึ้น Bing-Chao Huang และ Michael A. Langston ^{[ 15 ]} ได้นำเสนอขั้นตอนวิธี แบบ in-placeที่ตรงไปตรงมาและใช้เวลาเชิงเส้นเพื่อผสานรายการที่เรียงลำดับโดยใช้พื้นที่เพิ่มเติมคงที่ ทั้งคู่ใช้ผลงานของ Kronrod และคนอื่นๆ อัลกอริทึมนี้ผสานในเวลาเชิงเส้นและพื้นที่เพิ่มเติมคงที่ อัลกอริทึมนี้ใช้เวลาเฉลี่ยมากกว่าอัลกอริทึมการเรียงลำดับแบบผสานมาตรฐานเพียงเล็กน้อย โดยสามารถใช้ เซลล์หน่วยความจำเพิ่มเติมชั่วคราว O ( n )ได้น้อยกว่าสองเท่า แม้ว่าอัลกอริทึมนี้จะเร็วกว่าในทางปฏิบัติมาก แต่ก็ไม่เสถียรสำหรับบางรายการ แต่ด้วยการใช้แนวคิดที่คล้ายกัน พวกเขาสามารถแก้ปัญหานี้ได้ อัลกอริทึมแบบ in-place อื่นๆ ได้แก่ SymMerge ซึ่งใช้ เวลาทั้งหมด O (( n + m ) log( n + m ))และเสถียร^{[ 16 ]} การ เสียบอัลกอริทึมดังกล่าวเข้ากับการเรียงลำดับแบบผสานจะเพิ่มความซับซ้อนเป็นแบบไม่เชิงเส้นแต่ยังคงเป็นกึ่งเชิงเส้นO ( n (log n ) ² )
• แอปพลิเคชันจำนวนมากที่ใช้การเรียงลำดับภายนอกจะใช้รูปแบบการเรียงลำดับแบบผสาน (merge sorting) โดยที่ข้อมูลนำเข้าจะถูกแบ่งออกเป็นรายการย่อยจำนวนมากขึ้น ซึ่งในอุดมคติแล้วควรเป็นจำนวนรายการที่เมื่อผสานรวมกันแล้วยังคงทำให้ชุดหน้าหน่วยความจำ ที่กำลังประมวลผล อยู่พอดีกับหน่วยความจำหลัก
• การเรียงลำดับ แบบผสานบล็อก (Block Merge Sort)เป็นรูปแบบการผสานที่ทันสมัย ​​เสถียร เป็นเส้นตรง และผสานในตำแหน่งเดิมโดยจะสร้างส่วนของค่าที่ไม่ซ้ำกันเพื่อใช้เป็นพื้นที่สลับ
• สามารถลดพื้นที่ส่วนเกินลงเหลือO (√ n ) ได้ โดยใช้การค้นหาแบบไบนารีและการหมุน^{[ 17 ]}วิธีนี้ถูกนำมาใช้โดยไลบรารี C++ STL และ quadsort ^{[ 12 ]}
• อีกทางเลือกหนึ่งในการลดการคัดลอกไปยังหลายรายการคือการเชื่อมโยงฟิลด์ข้อมูลใหม่กับแต่ละคีย์ (องค์ประกอบในmเรียกว่าคีย์) ฟิลด์นี้จะใช้เพื่อเชื่อมโยงคีย์และข้อมูลที่เกี่ยวข้องเข้าด้วยกันในรายการที่เรียงลำดับแล้ว (คีย์และข้อมูลที่เกี่ยวข้องเรียกว่าเรคอร์ด) จากนั้นการรวมรายการที่เรียงลำดับแล้วจะดำเนินการโดยการเปลี่ยนค่าการเชื่อมโยง ไม่จำเป็นต้องย้ายเรคอร์ดใดๆ เลย ฟิลด์ที่มีเฉพาะการเชื่อมโยงโดยทั่วไปจะมีขนาดเล็กกว่าเรคอร์ดทั้งหมด ดังนั้นจึงใช้พื้นที่น้อยลงด้วย นี่เป็นเทคนิคการเรียงลำดับมาตรฐาน ไม่ได้จำกัดเฉพาะการเรียงลำดับแบบผสาน (merge sort) เท่านั้น
• วิธีง่ายๆ ในการลดพื้นที่ส่วนเกินให้เหลือn /2 คือการคง โครงสร้าง ซ้ายและขวาไว้เป็นโครงสร้างรวมกัน คัดลอกเฉพาะ ส่วน ซ้ายของmไปยังพื้นที่ชั่วคราว และสั่งให้ รูทีน การรวมวางผลลัพธ์ที่รวมแล้วลงในmด้วยวิธีนี้ การจัดสรรพื้นที่ชั่วคราวนอก รูทีน การรวม จะดีกว่า เพราะจะทำให้มีการจัดสรรเพียงครั้งเดียวเท่านั้น การคัดลอกที่มากเกินไปที่กล่าวถึงก่อนหน้านี้ก็ลดลงเช่นกัน เนื่องจากบรรทัดคู่สุดท้ายก่อน คำสั่ง ส่งคืนผลลัพธ์ (ฟังก์ชันmergeในรหัสเทียมด้านบน) กลายเป็นสิ่งที่ไม่จำเป็น

การ เรียงลำดับแบบผสาน ภายนอก (External merge sort) มีประโยชน์ในการใช้งานกับดิสก์หรือเทปไดรฟ์เมื่อข้อมูลที่จะเรียงลำดับมีขนาดใหญ่เกินกว่าจะเก็บไว้ในหน่วยความจำได้การเรียงลำดับภายนอกอธิบายวิธีการใช้งานการเรียงลำดับแบบผสานกับดิสก์ไดรฟ์ โดยทั่วไปแล้ว การเรียงลำดับบนเทปไดรฟ์จะใช้เทปไดรฟ์สี่ตัว การรับส่งข้อมูลทั้งหมดเป็นแบบเรียงลำดับ (ยกเว้นการกรอเทปกลับในตอนท้ายของแต่ละรอบ) การใช้งานแบบง่ายๆ สามารถทำได้โดยใช้บัฟเฟอร์บันทึกเพียงสองตัวและตัวแปรโปรแกรมเพียงไม่กี่ตัว

โดยตั้งชื่อไดรฟ์เทปทั้งสี่ตัวว่า A, B, C, D โดยที่ข้อมูลดั้งเดิมอยู่บนไดรฟ์ A และใช้บัฟเฟอร์บันทึกเพียงสองตัว อัลกอริทึมนี้จึงคล้ายกับการใช้งานแบบจากล่างขึ้นบนโดยใช้ไดรฟ์เทปเป็นคู่ๆ แทนที่จะใช้แถวในหน่วยความจำ อัลกอริทึมพื้นฐานสามารถอธิบายได้ดังนี้:

1. รวมคู่ระเบียนจาก A เข้าด้วยกัน โดยเขียนรายการย่อยสองระเบียนสลับกันไปยัง C และ D
2. รวมรายการย่อยสองรายการจาก C และ D เข้าด้วยกันเป็นรายการย่อยสี่รายการ แล้วเขียนสลับกันไปยัง A และ B
3. รวมรายการย่อยสี่รายการจาก A และ B เข้าด้วยกันเป็นรายการย่อยแปดรายการ แล้วเขียนสลับกันไปยัง C และ D
4. ทำซ้ำจนกว่าคุณจะมีรายการเดียวที่มีข้อมูลทั้งหมดเรียงลำดับแล้ว โดยใช้จำนวนรอบ log ₂ ( n ) รอบ

แทนที่จะเริ่มต้นด้วยชุดข้อมูลสั้นๆ มัก จะใช้ อัลกอริทึมแบบไฮบริดโดยที่การผ่านครั้งแรกจะอ่านเรคอร์ดจำนวนมากเข้าไปในหน่วยความจำ ทำการเรียงลำดับภายในเพื่อสร้างชุดข้อมูลยาว จากนั้นจึงกระจายชุดข้อมูลยาวเหล่านั้นไปยังชุดข้อมูลเอาต์พุต ขั้นตอนนี้ช่วยหลีกเลี่ยงการผ่านหลายครั้งในช่วงแรก ตัวอย่างเช่น การเรียงลำดับภายในของเรคอร์ด 1024 จะช่วยประหยัดการผ่านได้ 9 ครั้ง การเรียงลำดับภายในมักจะมีขนาดใหญ่เนื่องจากมีประโยชน์ดังกล่าว อันที่จริง มีเทคนิคที่สามารถทำให้ชุดข้อมูลเริ่มต้นยาวกว่าหน่วยความจำภายในที่มีอยู่ หนึ่งในนั้นคือ 'snowplow' ของ Knuth (ซึ่งอิงตามmin-heap แบบไบนารี ) ซึ่งสร้างชุดข้อมูลที่ยาวเป็นสองเท่า (โดยเฉลี่ย) ของขนาดหน่วยความจำที่ใช้^{[ 18 ]}

ด้วยค่าใช้จ่ายเพิ่มเติมเล็กน้อย อัลกอริทึมข้างต้นสามารถปรับเปลี่ยนให้ใช้เทปสามม้วนได้ เวลาในการทำงาน O ( n log n ) ก็สามารถทำได้โดยใช้คิวสองคิวหรือสแต็กและคิว หรือสแต็กสามอัน ในทางกลับกัน การใช้ เทปมากกว่า kม้วน (และ รายการ O ( k ) ในหน่วยความจำ) เราสามารถลดจำนวนการดำเนินการกับเทปได้เป็นO ( log k ) เท่า โดยใช้การผสานแบบ k/2 ทาง

การเรียงลำดับแบบผสานที่ซับซ้อนกว่า ซึ่งช่วยเพิ่มประสิทธิภาพการใช้งานเทป (และดิสก์) ไดรฟ์ คือการเรียงลำดับแบบผสานหลายเฟส (polyphase merge sort )

ในคอมพิวเตอร์สมัยใหม่หลักการอ้างอิงตำแหน่ง (locality of reference)มีความสำคัญอย่างยิ่งต่อการเพิ่มประสิทธิภาพซอฟต์แวร์เนื่องจากมีการใช้ลำดับชั้นหน่วยความจำ หลายระดับ จึงมีการเสนอเวอร์ชันของอัลกอริทึมการ เรียงลำดับแบบผสาน (merge sort) ที่คำนึงถึงแคช โดยมีการเลือกการทำงานเฉพาะเพื่อลดการเคลื่อนย้ายหน้าเข้าและออกจากแคชหน่วยความจำของเครื่องให้น้อยที่สุด ตัวอย่างเช่นอัลกอริ ทึมการเรียงลำดับแบบผสานแบบเรียงต่อกันจะหยุดการแบ่งส่วนย่อยของอาร์เรย์เมื่อถึงขนาด S โดยที่ S คือจำนวนรายการข้อมูลที่สามารถจัดเก็บในแคชของซีพียูได้ แต่ละอาร์เรย์ย่อยเหล่านี้จะถูกเรียงลำดับด้วยอัลกอริทึมการเรียงลำดับแบบในตัว เช่นแทรกเพื่อลดการสลับหน่วยความจำ และจากนั้นจึงทำการเรียงลำดับแบบผสานตามปกติโดยใช้การเรียกซ้ำแบบมาตรฐาน อัลกอริทึมนี้แสดงให้เห็นถึงประสิทธิภาพที่ดีกว่าบนเครื่องที่ได้รับประโยชน์จากการเพิ่มประสิทธิภาพแคช (LaMarca & Ladner 1997)

อัลกอริทึมการเรียง ลำดับแบบผสาน (Merge sort) สามารถประมวลผลแบบขนานได้ดีเนื่องจากใช้ วิธี การแบ่งและพิชิต (divide-and-conquer ) มีการพัฒนาอัลกอริทึมแบบขนานหลายรูปแบบขึ้นมาในช่วงหลายปีที่ผ่านมา อัลกอริทึมการเรียงลำดับแบบผสานแบบขนานบางแบบมีความเกี่ยวข้องอย่างมากกับอัลกอริทึมการผสานแบบบนลงล่าง (top-down merge) ที่ทำงานตามลำดับ ในขณะที่บางแบบมีโครงสร้างทั่วไปที่แตกต่างออกไปและใช้ วิธี การผสานแบบ K ทาง (K-way merge )

ขั้นตอนการเรียงลำดับแบบผสานตามลำดับสามารถอธิบายได้เป็นสองขั้นตอน คือ ขั้นตอนการแบ่งและขั้นตอนการผสาน ขั้นตอนแรกประกอบด้วยการเรียกซ้ำหลายครั้งที่ดำเนินการแบ่งซ้ำๆ จนกว่าลำดับย่อยจะถูกเรียงลำดับอย่างง่าย (มีองค์ประกอบหนึ่งหรือไม่มีเลย) แนวทางที่เข้าใจง่ายคือการขนานการเรียกซ้ำเหล่านั้น^{[ 19 ]}รหัสเทียมต่อไปนี้อธิบายการเรียงลำดับแบบผสานด้วยการเรียกซ้ำแบบขนานโดยใช้ คำหลัก fork และ join :

// เรียงลำดับองค์ประกอบ lo ถึง hi (ไม่รวม lo ) ของอาร์เรย์ A โดยใช้อัลกอริทึม mergesort(A, lo, hi) หาก lo+1 < hi แล้ว // จะมีองค์ประกอบสองตัวขึ้นไป mid := ⌊(lo + hi) / 2⌋ fork mergesort(A, lo, mid) mergesort(A, mid, hi) เข้าร่วม merge(A, lo, mid, hi) 

อัลกอริทึมนี้เป็นการดัดแปลงอย่างง่ายจากเวอร์ชันแบบลำดับ และไม่สามารถประมวลผลแบบขนานได้ดี ดังนั้นความเร็วที่เพิ่มขึ้นจึงไม่น่าประทับใจมากนัก มีช่วงการทำงานอยู่ที่ซึ่งเป็นการปรับปรุงเพียงเล็กน้อยเมื่อเทียบกับเวอร์ชันแบบลำดับ (ดูบทนำเกี่ยวกับอัลกอริทึม ) สาเหตุหลักมาจากวิธีการผสานแบบลำดับ ซึ่งเป็นคอขวดของการประมวลผลแบบขนาน ${\displaystyle \Theta (n)}$${\displaystyle \Theta (\log n)}$

สามารถบรรลุการทำงานแบบขนานที่ดีขึ้นได้โดยใช้อัลกอริธึมการรวมแบบขนานCormen และคณะนำเสนอรูปแบบไบนารีที่รวมลำดับย่อยที่เรียงลำดับแล้วสองลำดับเข้าเป็นลำดับเอาต์พุตที่เรียงลำดับแล้วหนึ่งลำดับ^{[ 19 ]}

ในลำดับหนึ่ง (ลำดับที่ยาวกว่าหากความยาวไม่เท่ากัน) จะเลือกองค์ประกอบที่มีดัชนีตรงกลาง ตำแหน่งขององค์ประกอบนั้นในลำดับอื่นจะถูกกำหนดในลักษณะที่ว่าลำดับนั้นจะยังคงเรียงลำดับอยู่หากแทรกองค์ประกอบนี้ลงในตำแหน่งนั้น ด้วยวิธีนี้ เราจะทราบจำนวนองค์ประกอบอื่น ๆ จากทั้งสองลำดับที่เล็กกว่า และสามารถคำนวณตำแหน่งขององค์ประกอบที่เลือกในลำดับผลลัพธ์ได้ สำหรับลำดับย่อยขององค์ประกอบที่เล็กกว่าและใหญ่กว่าที่สร้างขึ้นในลักษณะนี้ อัลกอริทึมการผสานจะถูกดำเนินการอีกครั้งแบบขนานจนกว่าจะถึงกรณีพื้นฐานของการเรียกซ้ำ

รหัสเทียมต่อไปนี้แสดงวิธีการเรียงลำดับแบบผสานขนานที่ได้รับการดัดแปลงโดยใช้อัลกอริธึมการผสานขนาน (ดัดแปลงจาก Cormen et al.)

/** * A: อาร์เรย์อินพุต * B: อาร์เรย์เอาต์พุต * lo: ขอบล่าง * hi: ขอบเขตบน * ปิด: ค่าชดเชย */ อัลกอริทึม parallelMergesort(A, lo, hi, B, off) คือ len := hi - lo + 1 ถ้า len == 1 แล้ว B[off] := A[lo] มิฉะนั้นให้ T[1..len] เป็นอาร์เรย์ใหม่ mid := ⌊(lo + hi) / 2⌋ mid' := mid - lo + 1 fork parallelMergesort(A, lo, mid, T, 1) parallelMergesort(A, mid + 1, hi, T, mid' + 1) เข้าร่วม parallelMerge(T, 1, mid', mid' + 1, len, B, off) 

เพื่อวิเคราะห์ความสัมพันธ์เวียนเกิดสำหรับช่วงกรณีที่เลวร้ายที่สุด จำเป็นต้องรวมการเรียกซ้ำของ parallelMergesort เพียงครั้งเดียวเท่านั้น เนื่องจากเป็นการทำงานแบบขนาน ทำให้ได้ผลลัพธ์ดังนี้

$${\displaystyle T_{\infty }^{\text{sort}}(n)=T_{\infty }^{\text{sort}}\left({\frac {n}{2}}\right)+T_{\infty }^{\text{merge}}(n)=T_{\infty }^{\text{sort}}\left({\frac {n}{2}}\right)+\Theta \left(\log(n)^{2}\right).}$$

สำหรับข้อมูลโดยละเอียดเกี่ยวกับความซับซ้อนของขั้นตอนการผสานแบบขนาน โปรดดู ที่ อั ลกอริทึมการผสาน

คำตอบของความสัมพันธ์เวียนเกิดนี้คือ

$${\displaystyle T_{\infty }^{\text{sort}}=\Theta \left(\log(n)^{3}\right).}$$

อัลกอริทึมการรวมแบบขนานนี้บรรลุระดับความขนานที่สูงกว่าระดับความขนานของอัลกอริทึมก่อนหน้ามาก การเรียงลำดับดังกล่าวสามารถทำงานได้ดีในทางปฏิบัติเมื่อรวมกับการเรียงลำดับแบบลำดับที่เสถียรและรวดเร็ว เช่นการเรียงลำดับแบบแทรกและการรวมแบบลำดับที่รวดเร็วเป็นกรณีพื้นฐานสำหรับการรวมอาร์เรย์ขนาดเล็ก^{[ 20 ]}${\textstyle \Theta \left({\frac {n}{(\log n)^{2}}}\right)}$

ดูเหมือนจะเป็นการจำกัดอัลกอริทึมการเรียงลำดับแบบผสานไว้ที่วิธีการผสานแบบไบนารีโดยพลการ เนื่องจากโดยปกติจะมีโปรเซสเซอร์ p > 2 ตัว วิธีการที่ดีกว่าอาจเป็นการใช้ วิธี การผสานแบบ K ทางซึ่งเป็นการขยายผลของการผสานแบบไบนารี โดยที่ลำดับที่เรียงลำดับแล้วจะถูกผสานเข้าด้วยกัน รูปแบบการผสานนี้เหมาะอย่างยิ่งสำหรับการอธิบายอัลกอริทึมการเรียงลำดับบนPRAM ^{[ 21 ] [ 22 ]}${\displaystyle k}$

กำหนดให้ลำดับขององค์ประกอบที่ไม่เรียงลำดับ เป้าหมายคือการเรียงลำดับลำดับนั้นโดยใช้โปรเซสเซอร์ที่มีอยู่องค์ประกอบเหล่านี้จะถูกกระจายอย่างเท่าเทียมกันในทุกโปรเซสเซอร์และเรียงลำดับในระดับท้องถิ่นโดยใช้อัลกอริธึมการเรียงลำดับ แบบลำดับ ดังนั้น ลำดับจึงประกอบด้วยลำดับที่เรียงลำดับแล้วซึ่งมีความยาวเพื่อความง่าย ให้เป็นพหุคูณของดังนั้นสำหรับ${\displaystyle n}$${\displaystyle p}$${\displaystyle S_{1},...,S_{p}}$${\textstyle \lceil {\frac {n}{p}}\rceil }$${\displaystyle n}$${\displaystyle p}$${\textstyle \left\vert S_{i}\right\vert ={\frac {n}{p}}}$${\displaystyle i=1,...,p}$

ลำดับเหล่านี้จะถูกนำมาใช้เพื่อทำการเลือกแบบหลายลำดับ/การเลือกตัวแบ่ง สำหรับอัลกอริธึม จะกำหนดองค์ประกอบตัวแบ่งที่มีอันดับทั่วโลกจากนั้นตำแหน่งที่สอดคล้องกันของในแต่ละลำดับจะถูกกำหนดด้วยการค้นหาแบบไบนารีและด้วยเหตุนี้จึงถูกแบ่งออกเป็นลำดับย่อยที่มี ${\displaystyle j=1,...,p}$${\displaystyle v_{j}}$${\textstyle k=j{\frac {n}{p}}}$${\displaystyle v_{1},...,v_{p}}$${\displaystyle S_{i}}$${\displaystyle S_{i}}$${\displaystyle p}$${\displaystyle S_{i,1},...,S_{i,p}}$${\textstyle S_{i,j}:=\{x\in S_{i}|rank(v_{j-1})<rank(x)\leq rank(v_{j})\}}$

นอกจากนี้ องค์ประกอบของจะถูกกำหนดให้กับโปรเซสเซอร์ซึ่งหมายความว่าองค์ประกอบทั้งหมดระหว่างอันดับและอันดับซึ่งกระจายอยู่ทั่วทุกโปรเซสเซอร์ ดังนั้น โปรเซสเซอร์แต่ละตัวจะได้รับลำดับของลำดับที่เรียงลำดับแล้ว ข้อเท็จจริงที่ว่าอันดับขององค์ประกอบตัวแยกถูกเลือกในระดับสากลนั้น มีคุณสมบัติที่สำคัญสองประการ: ประการแรก อันดับถูกเลือกเพื่อให้โปรเซสเซอร์แต่ละตัวยังคงสามารถทำงานกับองค์ประกอบได้หลังจากการกำหนด อัลกอริทึมจึงมีความสมดุลของภาระงาน อย่างสมบูรณ์ ประการ ที่สอง องค์ประกอบทั้งหมดในโปรเซสเซอร์จะมีค่าน้อยกว่าหรือเท่ากับองค์ประกอบทั้งหมดในโปรเซสเซอร์ดังนั้น โปรเซสเซอร์แต่ละตัวจึงทำการผสานแบบp ทาง ในระดับท้องถิ่น และได้รับลำดับที่เรียงลำดับจากลำดับย่อยของตนเอง เนื่องจากคุณสมบัติข้อที่สอง จึงไม่ จำเป็นต้องทำการผสานแบบ pทางเพิ่มเติม ผลลัพธ์จึงต้องนำมารวมกันตามลำดับหมายเลขของโปรเซสเซอร์เท่านั้น ${\displaystyle S_{1,i},...,S_{p,i}}$${\displaystyle i}$${\textstyle (i-1){\frac {n}{p}}}$${\textstyle i{\frac {n}{p}}}$${\displaystyle S_{i}}$${\displaystyle k}$${\displaystyle v_{i}}$${\displaystyle k}$${\textstyle n/p}$${\displaystyle i}$${\displaystyle i+1}$

ในรูปแบบที่ง่ายที่สุด เมื่อกำหนดลำดับที่เรียงแล้วซึ่งกระจายอย่างสม่ำเสมอในโปรเซสเซอร์และอันดับ (rank) งานคือการค้นหาองค์ประกอบที่มีอันดับสูงสุด (global rank) ในผลรวมของลำดับเหล่านั้น ดังนั้น จึงสามารถใช้สิ่งนี้เพื่อแบ่งแต่ละลำดับออกเป็นสองส่วนที่ดัชนีตัวแบ่ง (splitter index ) โดยส่วนล่างจะมีเฉพาะองค์ประกอบที่เล็กกว่าในขณะที่องค์ประกอบที่ใหญ่กว่าจะอยู่ในส่วนบน ${\displaystyle p}$${\displaystyle S_{1},...,S_{p}}$${\displaystyle p}$${\displaystyle k}$${\displaystyle x}$${\displaystyle k}$${\displaystyle S_{i}}$${\displaystyle l_{i}}$${\displaystyle x}$${\displaystyle x}$

อัลกอริทึมลำดับที่นำเสนอจะส่งคืนดัชนีของการแบ่งในแต่ละลำดับ เช่น ดัชนีในลำดับที่มีอันดับทั่วโลกน้อยกว่าและ^{[ 23 ]}${\displaystyle l_{i}}$${\displaystyle S_{i}}$${\displaystyle S_{i}[l_{i}]}$${\displaystyle k}$${\displaystyle \mathrm {rank} \left(S_{i}[l_{i}+1]\right)\geq k}$

อัลกอริทึม msSelect(S : อาร์เรย์ของลำดับที่เรียงลำดับแล้ว [S_1,..,S_p], k : จำนวนเต็ม) คือสำหรับ i = 1 ถึง p ทำ (l_i, r_i) = (0, |S_i|-1) ในขณะที่มี i อยู่: l_i < r_i ให้ทำ // เลือกองค์ประกอบ Pivotใน S_j[l_j], .., S_j[r_j] โดยเลือก j แบบสุ่มอย่างสม่ำเสมอ v := pickPivot(S, l, r) สำหรับ i = 1 ถึง p ทำ m_i = binarySearch(v, S_i[l_i, r_i]) // ตามลำดับ ถ้า m_1 + ... + m_p >= k แล้ว // m_1 + ... + m_p คืออันดับทั่วโลกของ v r := m // การกำหนดค่าเวกเตอร์ อื่น l := m ส่งคืน l 

สำหรับการวิเคราะห์ความซับซ้อนนั้น เลือกใช้โมเดล PRAMหากข้อมูลกระจายอย่างสม่ำเสมอทั่วทั้งการดำเนินการแบบ p-fold ของ เมธอด binarySearchจะใช้เวลาในการทำงานเท่ากับความลึกของการเรียกซ้ำที่คาดหวังจะเหมือนกับในQuickselect ทั่วไป ดังนั้นเวลาในการทำงานโดยรวมที่คาดหวังคือ ${\displaystyle p}$${\displaystyle {\mathcal {O}}\left(p\log \left(n/p\right)\right)}$${\displaystyle {\mathcal {O}}\left(\log \left(\textstyle \sum _{i}|S_{i}|\right)\right)={\mathcal {O}}(\log(n))}$${\displaystyle {\mathcal {O}}\left(p\log(n/p)\log(n)\right)}$

เมื่อนำอัลกอริธึมนี้ไปใช้กับอัลกอริทึมการเรียงลำดับแบบผสานหลายทางแบบขนาน จะต้องเรียกใช้แบบขนานเพื่อให้สามารถค้นหาองค์ประกอบตัวแบ่งทั้งหมดที่มีอันดับสำหรับได้พร้อมกัน จากนั้นจึงสามารถใช้องค์ประกอบตัวแบ่งเหล่านี้เพื่อแบ่งลำดับแต่ละลำดับออกเป็นส่วนๆ โดยใช้เวลาการทำงานรวมเท่าเดิม ${\textstyle i{\frac {n}{p}}}$${\displaystyle i=1,..,p}$${\displaystyle p}$${\displaystyle {\mathcal {O}}\left(p\,\log(n/p)\log(n)\right)}$

ด้านล่างนี้คือรหัสเทียม (pseudocode) ที่สมบูรณ์ของอัลกอริธึมการเรียงลำดับแบบผสานหลายทางแบบขนาน เราสมมติว่ามีการซิงโครไนซ์แบบกั้น (barrier synchronization) ก่อนและหลังการเลือกหลายลำดับ (multisequence selection) เพื่อให้โปรเซสเซอร์แต่ละตัวสามารถกำหนดองค์ประกอบการแบ่งและส่วนแบ่งลำดับได้อย่างถูกต้อง

/** * d: อาร์เรย์ขององค์ประกอบที่ไม่ได้เรียงลำดับ * n: จำนวนองค์ประกอบ * p: จำนวนโปรเซสเซอร์ * ส่งคืนอาร์เรย์ที่เรียงลำดับแล้ว */ algorithm parallelMultiwayMergesort(d : Array, n : int, p : int) is o := new Array[0, n] // อาร์เรย์ผลลัพธ์ for i = 1 to p do in parallel // แต่ละโปรเซสเซอร์ทำงานแบบขนาน S_i := d[(i-1) * n/p, i * n/p] // ลำดับที่มีความยาว n/p sort(S_i) // เรียงลำดับภายในเครื่อง ซิงค์ v_i := msSelect([S_1,...,S_p], i * n/p) // องค์ประกอบที่มีอันดับทั่วโลก i * n/p ซิงค์ (S_i,1, ..., S_i,p) := sequence_partitioning(si, v_1, ..., v_p) // แยก s_i ออกเป็นลำดับย่อย o[(i-1) * n/p, i * n/p] := kWayMerge(s_1,i, ..., s_p,i) // ผสานและกำหนดให้กับอาร์เรย์เอาต์พุต ส่งคืน o 

ขั้นแรก โปรเซสเซอร์แต่ละตัวจะเรียงลำดับองค์ประกอบที่ได้รับมอบหมายในพื้นที่โดยใช้อัลกอริธึมการเรียงลำดับที่มีความซับซ้อนหลังจากนั้น จะต้องคำนวณองค์ประกอบของตัวแยกในเวลาสุดท้าย แต่ละกลุ่มของการแยกจะต้องถูกรวมเข้าด้วยกันแบบขนานโดยโปรเซสเซอร์แต่ละตัวด้วยเวลาการทำงานโดยใช้อัลกอริธึมการรวมแบบลำดับ p ทางดังนั้น เวลาการทำงานโดยรวมจึงกำหนดโดย ${\displaystyle n/p}$${\displaystyle {\mathcal {O}}\left(n/p\;\log(n/p)\right)}$${\displaystyle {\mathcal {O}}\left(p\,\log(n/p)\log(n)\right)}$${\displaystyle p}$${\displaystyle {\mathcal {O}}(\log(p)\;n/p)}$

${\displaystyle {\mathcal {O}}\left({\frac {n}{p}}\log \left({\frac {n}{p}}\right)+p\log \left({\frac {n}{p}}\right)\log(n)+{\frac {n}{p}}\log(p)\right)}$.

อัลกอริทึมการเรียงลำดับแบบผสานหลายทาง (Multiway Merge Sort) มีความสามารถในการปรับขนาดได้สูงมากเนื่องจากความสามารถในการประมวลผลแบบขนานสูง ซึ่งช่วยให้สามารถใช้โปรเซสเซอร์จำนวนมากได้ ทำให้เป็นตัวเลือกที่เหมาะสมสำหรับการเรียงลำดับข้อมูลจำนวนมาก เช่น ข้อมูลที่ประมวลผลในคลัสเตอร์คอมพิวเตอร์นอกจากนี้ เนื่องจากในระบบดังกล่าว หน่วยความจำมักไม่ใช่ทรัพยากรที่จำกัด ข้อเสียของความซับซ้อนด้านพื้นที่ของอัลกอริทึมการเรียงลำดับแบบผสานจึงแทบไม่มีนัยสำคัญ อย่างไรก็ตาม ปัจจัยอื่นๆ ก็มีความสำคัญในระบบดังกล่าว ซึ่งไม่ได้นำมาพิจารณาเมื่อสร้างแบบจำลองบนPRAMในที่นี้ จำเป็นต้องพิจารณาประเด็นต่อไปนี้: ลำดับชั้นของหน่วยความจำเมื่อข้อมูลไม่สามารถจัดเก็บในแคชของโปรเซสเซอร์ได้ หรือค่าใช้จ่ายในการสื่อสารในการแลกเปลี่ยนข้อมูลระหว่างโปรเซสเซอร์ ซึ่งอาจกลายเป็นคอขวดเมื่อไม่สามารถเข้าถึงข้อมูลผ่านหน่วยความจำที่ใช้ร่วมกันได้อีกต่อไป

Sandersและคณะได้นำเสนอในบทความของพวกเขาถึง อัลกอริทึม แบบขนานซิงโครนัสจำนวนมากสำหรับการเรียงลำดับแบบผสานหลายระดับหลายทาง ซึ่งแบ่งโปรเซสเซอร์ออกเป็นกลุ่มที่มีขนาดโปรเซสเซอร์ทั้งหมดจะเรียงลำดับในพื้นที่ก่อน แตกต่างจากการเรียงลำดับแบบผสานหลายทางระดับเดียว ลำดับเหล่านี้จะถูกแบ่งออกเป็นส่วน ๆ และกำหนดให้กับกลุ่มโปรเซสเซอร์ที่เหมาะสม ขั้นตอนเหล่านี้จะถูกทำซ้ำแบบเรียกซ้ำในกลุ่มเหล่านั้น ซึ่งจะช่วยลดการสื่อสารและโดยเฉพาะอย่างยิ่งหลีกเลี่ยงปัญหาที่มีข้อความขนาดเล็กจำนวนมาก โครงสร้างลำดับชั้นของเครือข่ายจริงพื้นฐานสามารถใช้เพื่อกำหนดกลุ่มโปรเซสเซอร์ (เช่นแร็คคลัสเตอร์... ) ^{[ 22 ]}${\displaystyle p}$${\displaystyle r}$${\displaystyle p'}$${\displaystyle r}$

Merge sort เป็นหนึ่งในอัลกอริทึมการเรียงลำดับแรกๆ ที่บรรลุความเร็วที่เหมาะสมที่สุด โดยRichard Coleใช้อัลกอริทึมการสุ่มตัวอย่างย่อยที่ชาญฉลาดเพื่อให้แน่ใจว่า การรวม O (1) ^{[ 24 ]}อัลกอริทึมการเรียงลำดับแบบขนานที่ซับซ้อนอื่นๆ สามารถบรรลุขอบเขตเวลาเดียวกันหรือดีกว่าด้วยค่าคงที่ที่ต่ำกว่า ตัวอย่างเช่น ในปี 1991 David Powers ได้อธิบายquicksort แบบขนาน (และradix sort ที่เกี่ยวข้อง ) ที่สามารถทำงานได้ใน เวลา O ( log n ) บนเครื่องเข้าถึงแบบสุ่มขนานCRCW (PRAM) ที่มี โปรเซสเซอร์ n ตัว โดยการแบ่งพาร์ติชันโดยปริยาย^{[ 25 ]} Powers ยังแสดงให้เห็นเพิ่มเติมว่าเวอร์ชันแบบไปป์ไลน์ของBitonic Mergesort ของ Batcher ที่ เวลา O ((log n ) ^{2 ) บน} เครือข่ายการเรียงลำดับแบบผีเสื้อในทางปฏิบัติเร็วกว่า การเรียงลำดับ O (log n ) ของเขาบน PRAM และเขาให้การอภิปรายโดยละเอียดเกี่ยวกับค่าใช้จ่ายที่ซ่อนอยู่เมื่อเปรียบเทียบ radix และแบบขนาน^{[ 26 ]}

แม้ว่าheapsortจะมีขอบเขตเวลาเท่ากับ merge sort แต่ต้องการพื้นที่เสริมเพียง Θ(1) แทนที่จะเป็น Θ( n ) ของ merge sort บนสถาปัตยกรรมสมัยใหม่ทั่วไป การใช้งาน quicksort ที่มีประสิทธิภาพ มักจะทำงานได้ดีกว่า merge sort สำหรับการเรียงลำดับอาร์เรย์บน RAM ^{[ 27 ]} Quicksort เป็นที่นิยมเมื่อขนาดข้อมูลที่จะเรียงลำดับมีขนาดเล็กกว่า เนื่องจากความซับซ้อนของพื้นที่สำหรับ quicksort คือ O(log n ) ซึ่งช่วยให้ใช้ประโยชน์จากตำแหน่งแคชได้ดีกว่า merge sort (ซึ่งมีความซับซ้อนของพื้นที่ O(n)) ^{[ 27 ]}ในทางกลับกัน merge sort เป็นการเรียงลำดับที่เสถียรและมีประสิทธิภาพมากกว่าในการจัดการสื่อลำดับที่เข้าถึงช้า การเรียงลำดับแบบผสานมักเป็นตัวเลือกที่ดีที่สุดสำหรับการเรียงลำดับรายการเชื่อมโยง : ในสถานการณ์นี้ การนำการเรียงลำดับแบบผสานไปใช้ในลักษณะที่ต้องการพื้นที่เพิ่มเพียง Θ(1) นั้นค่อนข้างง่าย และประสิทธิภาพการเข้าถึงแบบสุ่มที่ช้าของรายการเชื่อมโยงทำให้บางอัลกอริธึมอื่นๆ (เช่น quicksort) ทำงานได้ไม่ดี และบางอัลกอริธึม (เช่น heapsort) เป็นไปไม่ได้เลย

ตั้งแต่Perl 5.8 เป็นต้นไป merge sort เป็นอัลกอริธึมการเรียงลำดับเริ่มต้น (ในเวอร์ชันก่อนหน้าของ Perl คือ quicksort) ^{[ 28 ]}ในJavaเมธอดArrays.sort()ใช้ merge sort หรือ quicksort ที่ปรับแต่งแล้ว ขึ้นอยู่กับชนิดข้อมูล และเพื่อประสิทธิภาพในการใช้งาน จะเปลี่ยนไปใช้insertion sortเมื่อมีองค์ประกอบในอาร์เรย์น้อยกว่าเจ็ดรายการที่กำลังเรียงลำดับ^{[ 29 ]}เคอร์เนล Linuxใช้merge sort สำหรับ linked lists ^{[ 30 ]}

Timsortซึ่งเป็นไฮบริดที่ปรับแต่งแล้วของ merge sort และ insertion sort ถูกใช้ในแพลตฟอร์มซอฟต์แวร์และภาษาต่างๆ รวมถึงแพลตฟอร์ม Java และ Android ^{[ 31 ]}และถูกใช้โดยPythonตั้งแต่เวอร์ชัน 2.3; ตั้งแต่เวอร์ชัน 3.11 นโยบายการรวมของ Timsort ได้รับการอัปเดตเป็นPowersort ^{[ 32 ]}

• คอร์เมน, โธมัส เอช. ; ไลเซอร์สัน, ชาร์ลส์ อี. ; ริเวสท์, โรนัลด์ แอล. ; สไตน์, คลิฟฟอร์ด (2009) [1990] ความรู้เบื้องต้นเกี่ยวกับอัลกอริทึม (ฉบับที่ 3) สำนักพิมพ์ MIT และ McGraw-Hill ไอเอสบีเอ็น 0-262-03384-4.
• Katajainen, Jyrki; Pasanen, Tomi; Teuhola, Jukka (1996). "Practical in-place mergesort" . Nordic Journal of Computing . 3 (1): 27– 40. CiteSeerX  10.1.1.22.8523 . ISSN  1236-6064 . เก็บถาวรจากต้นฉบับเมื่อ 2011-08-07 . สืบค้นเมื่อ2009-04-04 .นอกจากนี้Practical In-Place Mergesort . นอกจากนี้[3]
• Knuth, Donald (1998). "ส่วนที่ 5.2.4: การเรียงลำดับโดยการผสาน" การเรียงลำดับและการค้นหาศิลปะแห่งการเขียนโปรแกรมคอมพิวเตอร์เล่ม 3 (ฉบับที่ 2). Addison-Wesley. หน้า  158–168 . ISBN 0-201-89685-0.
• Kronrod, MA (1969). "อัลกอริทึมการเรียงลำดับที่เหมาะสมที่สุดโดยไม่มีฟิลด์การดำเนินการ". คณิตศาสตร์โซเวียต - Doklady . 10 : 744.
• LaMarca, A.; Ladner, RE (1997). "อิทธิพลของแคชต่อประสิทธิภาพของการเรียงลำดับ". Proc. 8th Ann. ACM-SIAM Symp. On Discrete Algorithms (SODA97) : 370– 379. CiteSeerX  10.1.1.31.1153 .
• Skiena, Steven S. (2008). "4.5: Mergesort: การเรียงลำดับโดยวิธีแบ่งและพิชิต". คู่มือการออกแบบอัลกอริทึม (ฉบับที่ 2). Springer. หน้า  120–125 . ISBN 978-1-84800-069-8.
• Sun Microsystems. "Arrays API (Java SE 6)" . สืบค้นเมื่อ2007-11-19 .
• Oracle Corp. "Arrays (Java SE 10 & JDK 10)" . สืบค้นเมื่อ2018-07-23 .

ใน Wikibook Algorithm implementationมีหน้าหนึ่งที่กล่าวถึงหัวข้อ: Merge sort

• ภาพเคลื่อนไหว แสดงอัลกอริทึมการเรียงลำดับ: การเรียงลำดับแบบผสาน (Merge Sort)ที่Wayback Machine (เก็บถาวรเมื่อวันที่ 6 มีนาคม 2015) – การสาธิตด้วยภาพกราฟิก
• Open Data Structures - ส่วนที่ 11.1.1 - การเรียงลำดับแบบผสาน (Merge Sort)โดยPat Morin
• โปรแกรมภาษาซีสำหรับใช้งานอัลกอริทึมการเรียงลำดับแบบผสาน (Merge Sort)
• ผสานรหัสเรียงลำดับด้วย Java
• โปรแกรม C++ สำหรับการเรียงลำดับแบบผสาน (Merge Sort)