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

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

1. ผลลัพธ์ที่ได้อยู่ใน ลำดับแบบ เอกพันธุ์ (แต่ละองค์ประกอบจะไม่เล็กหรือใหญ่กว่าองค์ประกอบก่อนหน้า ตามลำดับที่กำหนด)
2. ผลลัพธ์ที่ได้คือการเรียงสับเปลี่ยน (การเรียงลำดับใหม่ แต่ยังคงรักษาองค์ประกอบเดิมทั้งหมดไว้) ของข้อมูลที่ป้อนเข้ามา

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

นับตั้งแต่เริ่มมีการคำนวณ ปัญหาการเรียงลำดับได้ดึงดูดการวิจัยมากมาย อาจเป็นเพราะความซับซ้อนในการแก้ปัญหาอย่างมีประสิทธิภาพ แม้ว่าจะมีคำอธิบายที่เรียบง่ายและคุ้นเคยก็ตาม ในบรรดาผู้เขียนอัลกอริทึมการเรียงลำดับยุคแรก ๆ ในช่วงประมาณปี 1951 มีBetty Holbertonซึ่งทำงานเกี่ยวกับENIACและUNIVAC ^{[ 1 ] [ 2 ]}การเรียงลำดับแบบบับเบิลได้รับการวิเคราะห์ตั้งแต่ปี 1956 ^{[ 3 ]}อัลกอริทึมที่เหมาะสมที่สุดในเชิงอะซิมโทติกเป็นที่รู้จักกันมาตั้งแต่กลางศตวรรษที่ 20 – อัลกอริทึมใหม่ ๆ ยังคงถูกคิดค้นขึ้นเรื่อย ๆ โดยTimsort ที่ใช้กันอย่างแพร่หลาย มีอายุตั้งแต่ปี 2002 และlibrary sortได้รับการตีพิมพ์ครั้งแรกในปี 2006

อัลกอริทึมการเรียงลำดับแบบเปรียบเทียบมีข้อกำหนดพื้นฐานคือการเปรียบเทียบ อัลกอริทึมที่ไม่ใช้การเปรียบเทียบ เช่นการเรียงลำดับแบบนับอาจมีประสิทธิภาพดีกว่า ${\displaystyle n\log {n}-1.4427n+O(\log {n})}$

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

การเรียงลำดับอาร์เรย์ขนาดเล็กอย่างเหมาะสมที่สุด (โดยใช้การเปรียบเทียบและการสลับน้อยที่สุด) หรือรวดเร็วที่สุด (เช่น การคำนึงถึงรายละเอียดเฉพาะของเครื่อง) ยังคงเป็นปัญหาการวิจัยที่เปิดกว้าง โดยมีเพียงวิธีแก้ปัญหาที่ทราบสำหรับอาร์เรย์ขนาดเล็กมาก (น้อยกว่า 20 องค์ประกอบ) เท่านั้น ในทำนองเดียวกัน การเรียงลำดับอย่างเหมาะสมที่สุด (ตามคำจำกัดความต่างๆ) บนเครื่องขนานก็เป็นหัวข้อการวิจัยที่เปิดกว้างเช่น กัน

อัลกอริทึมการเรียงลำดับสามารถจำแนกได้ดังนี้:

• ความซับซ้อนในการคำนวณ
  • พฤติกรรม ในกรณีที่ดีที่สุด แย่ที่สุด และเฉลี่ยในแง่ของขนาดของรายการ สำหรับอัลกอริธึมการเรียงลำดับแบบอนุกรมทั่วไป พฤติกรรมที่ดีคือ O( n  log  n ) การเรียงลำดับแบบขนานคือ O(log ²  n ) และพฤติกรรมที่แย่คือ O( n ² ) พฤติกรรมในอุดมคติสำหรับการเรียงลำดับแบบอนุกรมคือ O( n ) แต่สิ่งนี้เป็นไปไม่ได้ในกรณีเฉลี่ย การเรียงลำดับแบบขนานที่เหมาะสมที่สุดคือ O(log  n )
  • การสลับเปลี่ยนสำหรับอัลกอริธึมแบบ "in-place"
• การใช้ หน่วยความจำ (และการใช้ทรัพยากรคอมพิวเตอร์อื่นๆ) โดยเฉพาะอย่างยิ่ง อัลกอริทึมการเรียงลำดับบางอย่างเป็นแบบ " in-place " ตามหลักแล้ว การเรียงลำดับแบบ in-place ต้องการหน่วยความจำเพียง O(1) นอกเหนือจากรายการที่กำลังเรียงลำดับ บางครั้งหน่วยความจำเพิ่มเติม O(log  n ) ก็ถือว่าเป็น "in-place" เช่นกัน
• การเรียกซ้ำ: อัลกอริทึมบางอย่างอาจเป็นแบบเรียกซ้ำโดยทั่วไป หรือแบบไม่เรียกซ้ำโดยทั่วไป ในขณะที่บางอย่างอาจเป็นทั้งสองอย่างโดยทั่วไป (เช่น การเรียงลำดับแบบผสาน)
• ความเสถียร: อัลกอริทึมการเรียงลำดับที่มีเสถียรภาพจะรักษาระดับลำดับสัมพัทธ์ของระเบียนที่มีคีย์ (เช่น ค่า) เท่ากัน
• ไม่ว่าจะเป็นการเรียงลำดับแบบเปรียบเทียบ หรือไม่ก็ตาม การเรียงลำดับแบบเปรียบเทียบจะตรวจสอบข้อมูลโดยการเปรียบเทียบองค์ประกอบสองตัวด้วยตัวดำเนินการเปรียบเทียบเท่านั้น
• วิธีการทั่วไป: การแทรก การสลับ การเลือก การรวมฯลฯการเรียงลำดับแบบสลับ ได้แก่ บับเบิลซอร์ตและควิกซอร์ต การเรียงลำดับแบบเลือก ได้แก่ ไซเคิลซอร์ตและฮีปซอร์ต
• ไม่ว่าอัลกอริทึมจะเป็นแบบอนุกรมหรือแบบขนาน ส่วนที่เหลือของการอธิบายนี้จะเน้นเฉพาะอัลกอริทึมแบบอนุกรมและสมมติว่าเป็นการทำงานแบบอนุกรมเป็นหลัก
• ความสามารถในการปรับตัว: การเรียงลำดับข้อมูลล่วงหน้ามีผลต่อเวลาในการทำงานหรือไม่ อัลกอริทึมที่คำนึงถึงเรื่องนี้เรียกว่าอัลกอริทึมที่ปรับตัวได้
• แบบออนไลน์: อัลกอริทึมอย่างเช่น Insertion Sort ที่ทำงานแบบออนไลน์ สามารถเรียงลำดับข้อมูลที่ป้อนเข้ามาอย่างต่อเนื่องได้

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

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

กล่าวอย่างเป็นทางการมากขึ้น ข้อมูลที่ต้องการเรียงลำดับสามารถแสดงได้ในรูปของระเบียนหรือคู่ของค่า และส่วนของข้อมูลที่ใช้ในการเรียงลำดับเรียกว่าคีย์ในตัวอย่างไพ่ ไพ่จะถูกแสดงเป็นระเบียน (ลำดับ, ดอกไพ่) และคีย์คือลำดับ อัลกอริทึมการเรียงลำดับจะเสถียรก็ต่อเมื่อเมื่อใดก็ตามที่มีระเบียน R และ S สองรายการที่มีคีย์เดียวกัน และ R ปรากฏก่อน S ในรายการเดิม R ก็จะปรากฏก่อน S ในรายการที่เรียงลำดับแล้วเสมอ

เมื่อองค์ประกอบที่เท่ากันไม่สามารถแยกแยะได้ เช่น ในกรณีของจำนวนเต็ม หรือโดยทั่วไปแล้ว ข้อมูลใดๆ ที่องค์ประกอบทั้งหมดเป็นคีย์ ความเสถียรจะไม่ใช่ปัญหา ความเสถียรก็ไม่ใช่ปัญหาเช่นกันหากคีย์ทั้งหมดแตกต่างกัน

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

หนึ่งในแอปพลิเคชันของอัลกอริธึมการเรียงลำดับแบบเสถียรคือการเรียงลำดับรายการโดยใช้คีย์หลักและคีย์รอง ตัวอย่างเช่น สมมติว่าเราต้องการเรียงลำดับไพ่ในมือให้ดอกไพ่เรียงตามลำดับคือ ดอกจิก (♣), ดอกข้าวหลามตัด ( ♦ ), ดอกหัวใจ ( ♥ ), ดอกโพธิ์ (♠) และภายในแต่ละดอกไพ่ ให้เรียงลำดับไพ่ตามแต้ม การทำเช่นนี้สามารถทำได้โดยการเรียงลำดับไพ่ตามแต้มก่อน (โดยใช้การเรียงลำดับใดก็ได้) จากนั้นจึงทำการเรียงลำดับแบบเสถียรตามดอกไพ่:

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

การวิเคราะห์นี้ตั้งอยู่บนสมมติฐานว่าความยาวของแต่ละคีย์มีค่าคงที่ และการเปรียบเทียบ การสลับ และการดำเนินการอื่นๆ ทั้งหมดสามารถดำเนินไปได้ในเวลาคงที่

ตำนาน:

• nคือจำนวนระเบียนที่จะต้องจัดเรียง
• คอลัมน์เปรียบเทียบมีการจัดอันดับดังนี้: "ดีที่สุด", "ปานกลาง" และ "แย่ที่สุด" หาก มีการระบุ ความซับซ้อนของเวลาสำหรับแต่ละกรณี
• "หน่วยความจำ" หมายถึงปริมาณพื้นที่จัดเก็บเพิ่มเติมที่จำเป็นสำหรับอัลกอริทึม
• เวลาในการทำงานและข้อกำหนดด้านหน่วยความจำที่ระบุไว้เขียนอยู่ในรูปแบบBig O Notationดังนั้นฐานของลอการิทึมจึงไม่สำคัญ
• สัญลักษณ์log ² nหมายถึง( log n ) ²

ด้านล่างนี้คือตาราง การเรียงลำดับ แบบเปรียบเทียบการวิเคราะห์ทางคณิตศาสตร์แสดงให้เห็นว่าการเรียงลำดับแบบเปรียบเทียบไม่สามารถทำงานได้ดีกว่าO ( n log n )โดยเฉลี่ย^{[ 4 ​​]}

การเรียงลำดับแบบเปรียบเทียบ

ชื่อ	ดีที่สุด	เฉลี่ย	แย่ที่สุด	หน่วยความจำ	มั่นคง	ในสถานที่	วิธี	หมายเหตุอื่นๆ
ฮีปซอร์ต	${\displaystyle n\log n}$	${\displaystyle n\log n}$	${\displaystyle n\log n}$	1	เลขที่	ใช่	การคัดเลือก	เป็นเวอร์ชันที่ปรับปรุงประสิทธิภาพของ Selection Sort โดยจะทำการ Selection Sort ด้วยการสร้างและบำรุงรักษา Max Heap เพื่อค้นหาค่าสูงสุดในเวลาที่เหมาะสม ${\displaystyle O(\log n)}$
อินโทรซอร์ต	${\displaystyle n\log n}$	${\displaystyle n\log n}$	${\displaystyle n\log n}$	${\displaystyle \log n}$	เลขที่	ใช่	การแบ่งพาร์ติชันและการเลือก	ใช้ใน รูปแบบการใช้งาน STL หลายแบบ ทำงานโดยการผสมผสานการเรียงลำดับแบบ Quicksort, Heapsort และ Insertion sort เข้าด้วยกัน
การเรียงลำดับแบบผสาน	${\displaystyle n\log n}$	${\displaystyle n\log n}$	${\displaystyle n\log n}$	n	ใช่	เลขที่	การควบรวม	สามารถขนานได้สูง (สูงสุดO (log n )โดยใช้อัลกอริทึมของชาวฮังการีสามคน) [ 5 ]
การเรียงลำดับแบบผสานในตัว	${\displaystyle n}$	${\displaystyle n\log ^{2}n}$	${\displaystyle n\log ^{2}n}$	${\displaystyle \log n}$	ใช่	ใช่	การควบรวม	รูปแบบหนึ่งของ Mergesort ที่ใช้ขั้นตอนวิธีผสานแบบเสถียรในตำแหน่งเดิม เช่น rotate merge หรือ symmerge ${\displaystyle O(n\log n)}$
การเรียงลำดับการแข่งขัน	${\displaystyle n\log n}$	${\displaystyle n\log n}$	${\displaystyle n\log n}$	n	ใช่	เลขที่	การคัดเลือก	เป็นการปรับปรุงประสิทธิภาพของ Selection Sort โดยใช้โครงสร้างต้นไม้แบบทัวร์นาเมนต์เพื่อเลือกค่าต่ำสุด/สูงสุด
การเรียงลำดับต้นไม้	${\displaystyle n\log n}$	${\displaystyle n\log n}$	${\displaystyle n\log n}$(สมดุล)	n	ใช่	เลขที่	การแทรก	เมื่อใช้โครงสร้างข้อมูลแบบ ต้นไม้ค้นหาไบนารีแบบปรับสมดุลตัวเอง
การเรียงลำดับแบบบล็อก	n	${\displaystyle n\log n}$	${\displaystyle n\log n}$	1	ใช่	ใช่	การแทรกและการรวม	รวมอัลกอริทึมการผสาน แบบin${\displaystyle O(n)}$ -place ที่ใช้บล็อก[ 6 ]เข้ากับ การ เรียง ลำดับการผสานแบบ bottom-up
สมูทซอร์ท	n	${\displaystyle n\log n}$	${\displaystyle n\log n}$	1	เลขที่	ใช่	การคัดเลือก	รูปแบบ ปรับตัวของฮีปซอร์ตโดยใช้ลำดับเลโอนาร์โดแทนฮีปไบนารี
ทิมซอร์ต	n	${\displaystyle n\log n}$	${\displaystyle n\log n}$	n	ใช่	เลขที่	การแทรกและการรวม	ทำการเปรียบเทียบเมื่อข้อมูลได้รับการจัดเรียงแล้วหรือจัดเรียงแบบย้อนกลับแล้ว ${\displaystyle n-1}$
การจัดเรียงความอดทน	n	${\displaystyle n\log n}$	${\displaystyle n\log n}$	n	เลขที่	เลขที่	การแทรกและการเลือก	ค้นหาลำดับย่อยที่เพิ่มขึ้นยาวที่สุด ทั้งหมด ในเวลา O ( n log n )
คิวบ์ซอร์ต	n	${\displaystyle n\log n}$	${\displaystyle n\log n}$	n	ใช่	เลขที่	การแทรก	ทำการเปรียบเทียบเมื่อข้อมูลได้รับการจัดเรียงแล้วหรือจัดเรียงแบบย้อนกลับแล้ว ${\displaystyle n-1}$
เรียงลำดับเร็ว	${\displaystyle n\log n}$	${\displaystyle n\log n}$	${\displaystyle n^{2}}$	${\displaystyle \log n}$	เลขที่	ใช่	การแบ่งพาร์ติชัน	Quicksort สามารถทำได้ในที่เดียวกันโดยใช้พื้นที่สแต็กO (log n ) [ 7 ] [ 8 ]
ฟลักซ์ซอร์ต	n	${\displaystyle n\log n}$	${\displaystyle n\log n}$	n	ใช่	เลขที่	การแบ่งพาร์ติชันและการรวม	การจัดเรียงภายในแบบปรับตัวได้และเสถียรโดยไม่แตกแขนง
ครัมซอร์ต	n	${\displaystyle n\log n}$	${\displaystyle n\log n}$	${\displaystyle \log n}$	เลขที่	ใช่	การแบ่งพาร์ติชันและการรวม	เป็นรูปแบบหนึ่งของ Fluxsort ที่ทำงานในตำแหน่งเดิม แต่ไม่เสถียร
การจัดเรียงห้องสมุด	${\displaystyle n\log n}$	${\displaystyle n\log n}$	${\displaystyle n^{2}}$	n	เลขที่	เลขที่	การแทรก	คล้ายกับการเรียงลำดับแบบแทรกที่มีช่องว่าง
เชลล์ซอร์ต	${\displaystyle n\log n}$	${\displaystyle \โอเมก้า (n\log n)}$	${\displaystyle O(n^{1+1/k})}$(เรขาคณิต) (แพรตต์)${\displaystyle n\log ^{2}n}$	1	เลขที่	ใช่	การแทรก	ขนาดโค้ดเล็ก ความซับซ้อนได้รับอิทธิพลจากลำดับช่องว่างที่ใช้ ลำดับของ Pratt เป็นกรณีที่เลวร้ายที่สุดซึ่งเป็นกรณีที่ทราบดีที่สุด ขอบเขตที่แน่นอนสำหรับค่าเฉลี่ยและกรณีที่เลวร้ายที่สุดยังคงเป็นปัญหาที่ยังไม่ได้รับการแก้ไข ${\displaystyle \Theta (n\log ^{2}n)}$
คัดแยกด้วยหวี	${\displaystyle n\log n}$	${\displaystyle n^{2}}$	${\displaystyle n^{2}}$	1	เลขที่	ใช่	การแลกเปลี่ยน	เร็วกว่าการเรียงลำดับแบบบับเบิลโดยเฉลี่ย
การเรียงลำดับแบบแทรก	n	${\displaystyle n^{2}}$	${\displaystyle n^{2}}$	1	ใช่	ใช่	การแทรก	O ( n + d )ในกรณีที่เลวร้ายที่สุดสำหรับลำดับที่มีการผกผันd ครั้ง
การเรียงลำดับแบบฟอง	n	${\displaystyle n^{2}}$	${\displaystyle n^{2}}$	1	ใช่	ใช่	การแลกเปลี่ยน	ขนาดโค้ดเล็กมาก
ประเภทเชคเกอร์ค็อกเทล	n	${\displaystyle n^{2}}$	${\displaystyle n^{2}}$	1	ใช่	ใช่	การแลกเปลี่ยน	รูปแบบการเรียงลำดับแบบสองทิศทางของ Bubblesort
โนมเรียงลำดับ	n	${\displaystyle n^{2}}$	${\displaystyle n^{2}}$	1	ใช่	ใช่	การแลกเปลี่ยน	ขนาดโค้ดเล็กมาก
การจัดเรียงเลขคี่-เลขคู่	n	${\displaystyle n^{2}}$	${\displaystyle n^{2}}$	1	ใช่	ใช่	การแลกเปลี่ยน	สามารถประมวลผลบนโปรเซสเซอร์แบบขนานได้อย่างง่ายดาย
การเรียงลำดับเส้นใย	n	${\displaystyle n^{2}}$	${\displaystyle n^{2}}$	n	ใช่	เลขที่	การคัดเลือก
การเรียงลำดับแบบเลือก	${\displaystyle n^{2}}$	${\displaystyle n^{2}}$	${\displaystyle n^{2}}$	1	เลขที่	ใช่	การคัดเลือก	ขนาดโค้ดเล็กมาก โดดเด่นด้วยความเรียบง่ายและจำนวนการเคลื่อนย้ายองค์ประกอบที่น้อย ทำการสลับตำแหน่ง ได้อย่างแม่นยำ${\displaystyle n-1}$
การเรียงลำดับแบบวงจร	${\displaystyle n^{2}}$	${\displaystyle n^{2}}$	${\displaystyle n^{2}}$	1	เลขที่	ใช่	การคัดเลือก	การเขียนข้อมูลลงในตำแหน่งเดิมโดยใช้จำนวนการเขียนที่เหมาะสมที่สุดในเชิงทฤษฎี

ตารางต่อไปนี้อธิบาย อัลกอริทึม การเรียงลำดับจำนวนเต็มและอัลกอริทึมการเรียงลำดับอื่นๆ ที่ไม่ใช่การเรียงลำดับแบบเปรียบเทียบอัลกอริทึมเหล่านี้ไม่จำกัดเฉพาะΩ ( n log n ) เว้นแต่จะตรงตามแบบจำลอง เครื่องจักรเข้าถึงแบบสุ่มต้นทุนต่อหน่วยตามที่อธิบายไว้ด้านล่าง^{[ 9 ]}

• ความซับซ้อนด้านล่างนี้สมมติว่ามี รายการที่จะเรียงลำดับจำนวน nรายการ โดยที่คีย์มีขนาดkขนาดของหลักคือdและช่วงของตัวเลขที่จะเรียงลำดับคือr
• วิธีการเหล่านี้จำนวนมากตั้งอยู่บนสมมติฐานที่ว่าขนาดของคีย์มีขนาดใหญ่พอที่จะทำให้ทุกรายการมีค่าคีย์ที่ไม่ซ้ำกัน และด้วยเหตุนี้n ≪ ^2kโดยที่≪หมายถึง "น้อยกว่ามาก"
• ใน แบบจำลอง เครื่องเข้าถึงแบบสุ่ม ต้นทุนต่อหน่วย อัลกอริทึมที่มีเวลาทำงานเช่น การเรียงลำดับแบบเรดิกซ์ ยังคงใช้เวลาตามสัดส่วนของΘ( n log n )เนื่องจากnถูกจำกัดไม่ให้เกินและจำนวนองค์ประกอบที่จะเรียงลำดับที่มากขึ้นจะต้องใช้k ที่ใหญ่ขึ้น เพื่อจัดเก็บในหน่วยความจำ^{[ 10 ]}${\displaystyle n\cdot {\frac {k}{d}}}$${\displaystyle 2^{\frac {k}{d}}}$

การเรียงลำดับที่ไม่ใช้การเปรียบเทียบ

ชื่อ	ดีที่สุด	เฉลี่ย	แย่ที่สุด	หน่วยความจำ	มั่นคง	n ≪ 2k	หมายเหตุ
การจัดเรียงแบบช่องๆ	—	${\displaystyle n+2^{k}}$	${\displaystyle n+2^{k}}$	${\displaystyle 2^{k}}$	ใช่	ใช่	ไม่สามารถเรียงลำดับตัวเลขที่ไม่ใช่จำนวนเต็มได้
การเรียงลำดับแบบ Bucket sort (โดยใช้คีย์ที่สม่ำเสมอ)	—	${\displaystyle n+k}$	${\displaystyle n^{2}\cdot k}$	${\displaystyle n\cdot k}$	ใช่	เลขที่	ถือว่าองค์ประกอบจากโดเมนในอาร์เรย์มีการกระจายอย่างสม่ำเสมอ[ 11 ] ไม่สามารถเรียงลำดับตัวเลขที่ไม่ใช่จำนวนเต็มได้เช่นกัน
การเรียงลำดับแบบ Bucket sort (คีย์เป็นจำนวนเต็ม)	—	${\displaystyle n+r}$	${\displaystyle n+r}$	${\displaystyle n+r}$	ใช่	ใช่	ถ้าrคือ⁠ ⁠${\displaystyle O(n)}$แล้วความซับซ้อนของเวลาเฉลี่ยคือ⁠ ⁠ ${\displaystyle O(n)}$[ 12 ]
การเรียงลำดับแบบนับ	—	${\displaystyle n+r}$	${\displaystyle n+r}$	${\displaystyle n+r}$	ใช่	ใช่	ถ้าrคือ⁠ ⁠${\displaystyle O(n)}$แล้วความซับซ้อนของเวลาเฉลี่ยคือ⁠ ⁠ ${\displaystyle O(n)}$[ 11 ]
ราก LSD คัดแยก	${\displaystyle n\cdot {\frac {k}{d}}}$	${\displaystyle n\cdot {\frac {k}{d}}}$	${\displaystyle n\cdot {\frac {k}{d}}}$	${\displaystyle n+2^{d}}$	ใช่	เลขที่	${\displaystyle {\frac {k}{d}}}$ระดับการเรียกซ้ำ 2 มิติสำหรับอาร์เรย์นับ[ 11 ] [ 12 ] แตกต่างจากวิธีการเรียงลำดับแบบกระจายส่วนใหญ่ วิธีการนี้สามารถเรียงลำดับตัวเลขที่ไม่ใช่จำนวนเต็มได้
MSD Radix Sort	${\displaystyle n}$	${\displaystyle n\cdot {\frac {k}{d}}}$	${\displaystyle n\cdot {\frac {k}{d}}}$	${\displaystyle n+2^{d}}$	ใช่	เลขที่	เวอร์ชันเสถียรใช้อาร์เรย์ภายนอกขนาดnเพื่อจัดเก็บถังทั้งหมด เช่นเดียวกับเวอร์ชัน LSD มันสามารถเรียงลำดับข้อมูลที่ไม่ใช่จำนวนเต็มได้
MSD Radix Sort (in-place)	${\displaystyle n}$	${\displaystyle n\cdot {\frac {k}{1}}}$	${\displaystyle n\cdot {\frac {k}{1}}}$	${\displaystyle 2^{1}}$	เลขที่	เลขที่	d=1 สำหรับระดับการเรียกซ้ำแบบ in-place โดยไม่มีอาร์เรย์นับจำนวน ${\displaystyle k/1}$
สเปรดซอร์ต	n	${\displaystyle n\cdot {\frac {k}{d}}}$	${\displaystyle n\cdot \left({{\frac {k}{s}}+d}\right)}$	${\displaystyle {\frac {k}{d}}\cdot 2^{d}}$	เลขที่	เลขที่	การหาค่าประมาณเชิงอะซิมโทติกนั้นตั้งอยู่บนสมมติฐานที่ว่าn ≪ 2k แต่ขั้นตอนวิธีนี้ไม่จำเป็นต้องใช้สมมติฐานนี้
เบิร์สต์ซอร์ต	—	${\displaystyle n\cdot {\frac {k}{d}}}$	${\displaystyle n\cdot {\frac {k}{d}}}$	${\displaystyle n\cdot {\frac {k}{d}}}$	เลขที่	เลขที่	มีค่าคงที่ที่ดีกว่าการเรียงลำดับแบบ Radix สำหรับการเรียงลำดับสตริง แม้ว่าจะขึ้นอยู่กับลักษณะเฉพาะของสตริงที่พบเจอทั่วไปอยู่บ้างก็ตาม
แฟลชซอร์ต	n	${\displaystyle n+r}$	${\displaystyle n^{2}}$	n	เลขที่	เลขที่	จำเป็นต้องมีการกระจายตัวอย่างสม่ำเสมอขององค์ประกอบจากโดเมนในอาร์เรย์เพื่อให้ทำงานได้ในเวลาเชิงเส้น หากการกระจายตัวเบี่ยงเบนอย่างมาก อาจใช้เวลาแบบกำลังสองหากการเรียงลำดับพื้นฐานเป็นแบบกำลังสอง (โดยปกติจะเป็นการเรียงลำดับแบบแทรก) เวอร์ชันที่ทำงานในตำแหน่งเดิมไม่เสถียร

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

อัลกอริทึมบางตัวทำงานช้ากว่าอัลกอริทึมที่กล่าวถึงข้างต้น เช่นbogosortที่มีเวลาทำงานไม่จำกัด และ^stooge sortซึ่งมี เวลาทำงาน O ( n²⁷ ) โดยปกติแล้วอัลกอริทึมเหล่านี้จะถูกอธิบายเพื่อจุดประสงค์ทางการศึกษา เพื่อแสดงให้เห็นถึงวิธีการประมาณเวลาทำงานของอัลกอริทึม ตารางต่อไปนี้อธิบายอัลกอริทึมการเรียงลำดับบางตัวที่ไม่สามารถนำไปใช้ได้จริงในบริบทซอฟต์แวร์แบบดั้งเดิม เนื่องจากประสิทธิภาพที่ต่ำมากหรือข้อกำหนดด้านฮาร์ดแวร์เฉพาะทาง

ชื่อ	ดีที่สุด	เฉลี่ย	แย่ที่สุด	หน่วยความจำ	มั่นคง	การเปรียบเทียบ	หมายเหตุอื่นๆ
การคัดแยกลูกปัด	n	เอส	เอส	${\displaystyle n^{2}}$	—ไม่มีข้อมูล	เลขที่	ใช้งานได้เฉพาะกับจำนวนเต็มบวกเท่านั้น ต้องใช้ฮาร์ดแวร์เฉพาะทางเพื่อให้ทำงานได้ในเวลาที่รับประกันได้มีความ${\displaystyle O(n)}$เป็นไปได้ที่จะเขียนโปรแกรม แต่เวลาในการทำงานจะนานมากโดย${\displaystyle O(S)}$ที่Sคือผลรวมของจำนวนเต็มทั้งหมดที่จะเรียงลำดับ ในกรณีที่จำนวนเต็มมีขนาดเล็ก อาจถือได้ว่าเป็นการเรียงลำดับเชิงเส้น
การเรียงลำดับแบบผสานและแทรก	${\displaystyle n\log n}$การเปรียบเทียบ	${\displaystyle n\log n}$การเปรียบเทียบ	${\displaystyle n\log n}$การเปรียบเทียบ	แตกต่างกันไป	เลขที่	ใช่	มีการเปรียบเทียบกรณีที่เลวร้ายที่สุดกับอัลกอริทึมการเรียงลำดับอื่นๆ น้อยมาก ส่วนใหญ่แล้วมีประโยชน์ในเชิงทฤษฎีเท่านั้น เนื่องจากความซับซ้อนในการนำไปใช้งานและการเคลื่อนย้ายข้อมูลที่ไม่เหมาะสม
สปาเก็ตตี้ (โพล) เรียงลำดับ	n	n	n	${\displaystyle n^{2}}$	ใช่	การสำรวจความคิดเห็น	นี่คืออัลกอริธึมแบบอนาล็อกที่ใช้เวลาเชิงเส้นสำหรับการเรียงลำดับรายการ โดยใช้ พื้นที่สแต็ก O ( n ) และการเรียงลำดับนั้นเสถียร ซึ่งต้องใช้โปรเซสเซอร์แบบขนานn ตัว ดูรายละเอียดเพิ่มเติมได้ที่ spaghetti sort § Analysis
เครือข่ายการคัดแยก	แตกต่างกันไป	แตกต่างกันไป	แตกต่างกันไป	แตกต่างกันไป	แตกต่างกันไป (เครือข่ายการเรียงลำดับที่เสถียรต้องการการเปรียบเทียบมากกว่า)	ใช่	ลำดับการเปรียบเทียบถูกกำหนดไว้ล่วงหน้าโดยอิงจากขนาดเครือข่ายที่กำหนดไว้
เครื่องคัดแยกบิโทนิก	${\displaystyle \log ^{2}n}$ขนาน	${\displaystyle \log ^{2}n}$ขนาน	${\displaystyle n\log ^{2}n}$ไม่ขนาน	1	เลขที่	ใช่	รูปแบบที่มีประสิทธิภาพของเครือข่ายการจัดเรียงข้อมูล
โบโกซอร์ท	n	${\displaystyle (n\times n!)}$	ไร้ขอบเขต	1	เลขที่	ใช่	การสับเปลี่ยนแบบสุ่ม ใช้เพื่อเป็นตัวอย่างเท่านั้น เนื่องจากแม้แต่เวลาการทำงานที่ดีที่สุดที่คาดหวังไว้ก็ยังแย่มาก[ 13 ] กรณีที่เลวร้ายที่สุดนั้นไม่มีขอบเขตจำกัดเมื่อใช้การสุ่ม แต่เวอร์ชันแบบกำหนดได้จะรับประกันว่ากรณีที่เลวร้ายที่สุดจะเกิดขึ้นอย่างแน่นอน ${\displaystyle O(n\times n!)}$
ตัวตลก	${\displaystyle n^{\log 3/\log 1.5}}$	${\displaystyle n^{\log 3/\log 1.5}}$	${\displaystyle n^{\log 3/\log 1.5}}$	${\displaystyle \log n}$	เลขที่	ใช่	ช้ากว่าอัลกอริธึมการเรียงลำดับส่วนใหญ่ (แม้แต่แบบพื้นฐาน) ด้วยความซับซ้อนของเวลาO ( n log 3 / log 1.5 ) = O ( n 2.7095... )สามารถทำให้เสถียรได้ และยังเป็นเครือข่ายการเรียงลำดับอีก ด้วย
สโลว์ซอร์ต	${\displaystyle o\left(n^{\log _{2}(n)/2}\right)}$	${\displaystyle o\left(n^{\log _{2}(n)/2}\right)}$	${\displaystyle o\left(n^{\log _{2}(n)/2}\right)}$	n	เลขที่	ใช่	อัลกอริทึมแบบคูณแล้วยอมแพ้ ซึ่งตรงข้ามกับอัลกอริทึมแบบแบ่งและพิชิต

นักวิทยาศาสตร์คอมพิวเตอร์เชิงทฤษฎีได้คิดค้นอัลกอริธึมการเรียงลำดับอื่นๆ ที่ให้ความซับซ้อนของเวลาที่ดีกว่าO ( n log n ) โดยสมมติข้อจำกัดบางประการ ซึ่งรวมถึง:

• อัลกอริทึมของ Thorup ^{[ 14 ]} อัลกอริ ทึมการเรียงลำดับจำนวนเต็มแบบสุ่มใช้เวลาO ( n log log n ) และ พื้นที่O ( n ) ^{[ 14 ]}
• อัลกอริทึม AHNR ^{[ 15 ]}เป็น อัลกอริทึม การเรียงลำดับจำนวนเต็มซึ่งทำงานในเวลาที่กำหนด และยังมีเวอร์ชันแบบสุ่มซึ่งทำงานในเวลาเชิงเส้นเมื่อคำมีขนาดใหญ่พอ โดยเฉพาะ(โดยที่wคือขนาดของคำ)${\displaystyle O(n\log \log n)}$${\displaystyle w\geq (\log n)^{2+\varepsilon }}$
• อัลกอริ ทึมการเรียงลำดับจำนวนเต็มแบบสุ่มใช้เวลาที่คาดหวังและพื้นที่O ( n ) ^{[ 16 ]}${\displaystyle O\left(n{\sqrt {\log \log n}}\right)}$

แม้ว่าจะมีอัลกอริทึมการเรียงลำดับอยู่มากมาย แต่ในการใช้งานจริงนั้นมีอัลกอริทึมเพียงไม่กี่ตัวที่ได้รับความนิยม การเรียงลำดับแบบแทรก (Insertion sort) ถูกใช้กันอย่างแพร่หลายสำหรับชุดข้อมูลขนาดเล็ก ในขณะที่สำหรับชุดข้อมูลขนาดใหญ่ จะใช้การเรียงลำดับที่มีประสิทธิภาพเชิงอะซิมโทติก (asymptotically efficient sort) โดยหลักๆ คือ ฮีปซอร์ต (heapsort), ผสานซอร์ต (merge sort) หรือ ควิกซอร์ต (quicksort) การใช้งานที่มีประสิทธิภาพโดยทั่วไปจะใช้อัลกอริทึมแบบผสมผสานโดยรวมอัลกอริทึมที่มีประสิทธิภาพเชิงอะซิมโทติกสำหรับการเรียงลำดับโดยรวมเข้ากับการเรียงลำดับแบบแทรกสำหรับรายการขนาดเล็กที่อยู่ด้านล่างสุดของการเรียกซ้ำ การใช้งานที่ปรับแต่งอย่างละเอียดจะใช้รูปแบบที่ซับซ้อนกว่า เช่นTimsort (ผสานซอร์ต การเรียงลำดับแบบแทรก และตรรกะเพิ่มเติม) ซึ่งใช้ในAndroid , JavaและPythonและIntrosort (ควิกซอร์ตและฮีปซอร์ต) ซึ่งใช้ (ในรูปแบบต่างๆ) ใน การใช้งานการ เรียงลำดับใน C++ บางส่วน และใน. NET

สำหรับข้อมูลที่มีข้อจำกัดมากขึ้น เช่น ตัวเลขในช่วงคงที่การเรียงลำดับแบบกระจายเช่น การเรียงลำดับแบบนับ หรือการเรียงลำดับแบบฐาน จะถูกนำมาใช้กันอย่างแพร่หลาย การเรียงลำดับแบบฟองสบู่และรูปแบบต่างๆ นั้นไม่ค่อยได้ใช้ในทางปฏิบัติ แต่พบเห็นได้ทั่วไปในการสอนและการอภิปรายเชิงทฤษฎี

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

การเรียงลำดับที่ง่ายที่สุดสองแบบคือ การเรียงลำดับแบบแทรก (insertion sort) และการเรียงลำดับแบบเลือก (selection sort) ซึ่งทั้งสองแบบมีประสิทธิภาพกับข้อมูลขนาดเล็ก เนื่องจากมีค่าใช้จ่ายในการทำงานต่ำ แต่ไม่มีประสิทธิภาพกับข้อมูลขนาดใหญ่ โดยทั่วไปแล้ว การเรียงลำดับแบบแทรกจะเร็วกว่าการเรียงลำดับแบบเลือกในทางปฏิบัติ เนื่องจากมีการเปรียบเทียบน้อยกว่าและมีประสิทธิภาพที่ดีกับข้อมูลที่เกือบเรียงลำดับแล้ว ดังนั้นจึงนิยมใช้มากกว่า แต่การเรียงลำดับแบบเลือกมีการเขียนข้อมูลน้อยกว่า จึงใช้เมื่อประสิทธิภาพการเขียนข้อมูลเป็นปัจจัยจำกัด

การเรียงลำดับ แบบแทรก (Insertion sort)เป็นอัลกอริทึมการเรียงลำดับแบบง่ายๆ ที่มีประสิทธิภาพค่อนข้างดีสำหรับรายการขนาดเล็กและรายการที่เรียงลำดับแล้วเป็นส่วนใหญ่ และมักใช้เป็นส่วนหนึ่งของอัลกอริทึมที่ซับซ้อนกว่า โดยทำงานโดยการนำองค์ประกอบจากรายการทีละรายการและแทรกเข้าไปในตำแหน่งที่ถูกต้องในรายการที่เรียงลำดับใหม่ คล้ายกับการใส่เงินลงในกระเป๋าเงิน ^{[ 17 ]}ในอาร์เรย์ รายการใหม่และองค์ประกอบที่เหลือสามารถใช้พื้นที่ของอาร์เรย์ร่วมกันได้ แต่การแทรกมีค่าใช้จ่ายสูง เนื่องจากต้องเลื่อนองค์ประกอบที่ตามมาทั้งหมดไปหนึ่งตำแหน่ง Shellsortเป็นรูปแบบหนึ่งของการเรียงลำดับแบบแทรกที่มีประสิทธิภาพมากกว่าสำหรับรายการขนาดใหญ่

การเรียงลำดับแบบเลือก (Selection sort)เป็นการเรียงลำดับแบบเปรียบเทียบแบบในตัว (in-place comparison sort) มี ความซับซ้อน O ( n² ⁾ทำให้ไม่มีประสิทธิภาพกับรายการขนาดใหญ่ และโดยทั่วไปแล้วจะมีประสิทธิภาพแย่กว่าการเรียงลำดับแบบแทรก (Insertion sort ) ที่คล้ายกัน การเรียงลำดับแบบเลือกนั้นโดดเด่นในด้านความเรียบง่าย และยังมีข้อได้เปรียบด้านประสิทธิภาพเหนืออัลกอริทึมที่ซับซ้อนกว่าในบางสถานการณ์

อัลกอริทึมจะค้นหาค่าต่ำสุด สลับค่าดังกล่าวกับค่าในตำแหน่งแรก และทำซ้ำขั้นตอนเหล่านี้สำหรับส่วนที่เหลือของรายการ^{[ 18 ]}โดยจะทำการสลับไม่เกินnครั้ง ดังนั้นจึงมีประโยชน์ในกรณีที่การสลับมีค่าใช้จ่ายสูงมาก

อัลกอริทึมการเรียงลำดับทั่วไปที่ใช้งานได้จริงเกือบทั้งหมดมักใช้พื้นฐานจากอัลกอริทึมที่มีความซับซ้อนของเวลาเฉลี่ย (และโดยทั่วไปคือความซับซ้อนในกรณีที่เลวร้ายที่สุด) O( n log n ) ซึ่งที่พบได้บ่อยที่สุดคือ heapsort, merge sort และ quicksort แต่ละอัลกอริทึมมีข้อดีและข้อเสีย โดยข้อเสียที่สำคัญที่สุดคือ การใช้งาน merge sort แบบง่ายจะใช้พื้นที่เพิ่มเติม O( n ) และการใช้งาน quicksort แบบง่ายมีความซับซ้อนในกรณีที่เลวร้ายที่สุด O( n² ⁾ปัญหาเหล่านี้สามารถแก้ไขหรือปรับปรุงได้โดยแลกกับอัลกอริทึมที่ซับซ้อนกว่า

แม้ว่าอัลกอริธึมเหล่านี้จะมีประสิทธิภาพเชิงอะซิมโทติกบนข้อมูลสุ่ม แต่เพื่อให้ได้ประสิทธิภาพในทางปฏิบัติบนข้อมูลจริง จึงจำเป็นต้องมีการปรับเปลี่ยนต่างๆ ประการแรก ค่าใช้จ่ายของอัลกอริธึมเหล่านี้จะสูงขึ้นอย่างมากเมื่อข้อมูลมีขนาดเล็ก ดังนั้นจึงมักใช้อัลกอริธึมแบบผสม โดยมักจะเปลี่ยนไปใช้การเรียงลำดับแบบแทรกเมื่อข้อมูลมีขนาดเล็กพอ ประการที่สอง อัลกอริธึมเหล่านี้มักทำงานได้ไม่ดีกับข้อมูลที่เรียงลำดับแล้วหรือข้อมูลที่เกือบเรียงลำดับแล้ว ซึ่งเป็นเรื่องปกติในข้อมูลจริงและสามารถเรียงลำดับได้ในเวลา O( n ) โดยใช้อัลกอริธึมที่เหมาะสม สุดท้าย อัลกอริธึมเหล่านี้อาจไม่เสถียรและความเสถียรเป็นคุณสมบัติที่พึงประสงค์ในการเรียงลำดับ ดังนั้นจึงมักใช้อัลกอริธึมที่ซับซ้อนกว่า เช่นTimsort (อิงจาก merge sort) หรือintrosort (อิงจาก quicksort โดยใช้ heapsort เป็นตัวเลือกสำรอง)

การเรียงลำดับแบบผสาน (Merge sort)ใช้ประโยชน์จากความง่ายในการผสานรายการที่เรียงลำดับแล้วเข้ากับรายการที่เรียงลำดับใหม่ โดยเริ่มจากการเปรียบเทียบองค์ประกอบสองรายการ (เช่น 1 กับ 2 จากนั้น 3 กับ 4...) และสลับตำแหน่งหากรายการแรกควรอยู่หลังรายการที่สอง จากนั้นจะผสานรายการที่ได้สองรายการแต่ละรายการเข้ากับรายการสี่รายการ จากนั้นผสานรายการสี่รายการเหล่านั้นต่อไปเรื่อยๆ จนกระทั่งรายการสองรายการสุดท้ายถูกผสานเข้ากับรายการที่เรียงลำดับสุดท้าย^{[ 19 ]}ในบรรดาอัลกอริทึมที่อธิบายไว้ที่นี่ นี่เป็นอัลกอริทึมแรกที่สามารถปรับขนาดได้ดีกับรายการขนาดใหญ่มาก เนื่องจากเวลาการทำงานในกรณีที่เลวร้ายที่สุดคือ O( n log n ) นอกจากนี้ยังสามารถนำไปใช้กับรายการได้ง่าย ไม่ใช่แค่กับอาร์เรย์เท่านั้น เนื่องจากต้องการเพียงการเข้าถึงตามลำดับ ไม่ใช่การเข้าถึงแบบสุ่ม เมื่อเรียงลำดับอาร์เรย์ จะมีความซับซ้อนของพื้นที่เพิ่มเติม O( n ) และเกี่ยวข้องกับการคัดลอกจำนวนมากในการใช้งานแบบง่าย อย่างไรก็ตามรายการเชื่อมโยงสามารถเรียงลำดับแบบผสานได้โดยใช้พื้นที่เพิ่มเติมคงที่ ดังนั้นจึงเป็นอัลกอริทึมที่เลือกใช้สำหรับการเรียงลำดับรายการเชื่อมโยง

การเรียงลำดับแบบผสาน (Merge sort) ได้รับความนิยมเพิ่มขึ้นอย่างมากในช่วงไม่นานมานี้สำหรับการนำไปใช้ในทางปฏิบัติ เนื่องจากมีการใช้ในอัลกอริทึมที่ซับซ้อนอย่างTimsortซึ่งใช้สำหรับขั้นตอนการเรียงลำดับมาตรฐานในภาษาโปรแกรมPython ^{[ 20 ]}และJava (ตั้งแต่JDK7 ^{[ 21 ]} เป็นต้นไป ) การเรียงลำดับแบบผสานเองก็เป็นขั้นตอนมาตรฐานในPerl [ ^{22 ] และ}ภาษาอื่นๆ อีกมากมาย และถูกใช้ใน Java อย่างน้อยตั้งแต่ปี 2000 ในJDK1.3 ^{[ 23 ]}

Heapsortเป็นเวอร์ชันที่มีประสิทธิภาพมากกว่าSelection Sort มาก โดยทำงานด้วยการหาองค์ประกอบที่ใหญ่ที่สุด (หรือเล็กที่สุด) ของรายการ แล้วนำไปวางไว้ที่ท้าย (หรือต้น) ของรายการ จากนั้นจึงดำเนินการต่อกับส่วนที่เหลือของรายการ แต่ทำงานนี้ได้อย่างมีประสิทธิภาพโดยใช้โครงสร้างข้อมูลที่เรียกว่าฮีป ซึ่งเป็น ต้นไม้ไบนารีชนิดพิเศษ^{[ 24 ]}เมื่อรายการข้อมูลถูกสร้างเป็นฮีปแล้ว โหนดรากจะรับประกันได้ว่าเป็นองค์ประกอบที่ใหญ่ที่สุด (หรือเล็กที่สุด) เมื่อถูกลบออกและวางไว้ที่ท้ายรายการ ฮีปจะถูกจัดเรียงใหม่เพื่อให้องค์ประกอบที่ใหญ่ที่สุดที่เหลืออยู่ย้ายไปที่ราก การใช้ฮีปทำให้การค้นหาองค์ประกอบที่ใหญ่ที่สุดถัดไปใช้เวลา O(log n ) แทนที่จะเป็น O( n ) สำหรับการสแกนเชิงเส้นเช่นเดียวกับ Selection Sort แบบง่าย ซึ่งทำให้ Heapsort ทำงานได้ในเวลา O( n log n ) และนี่คือความซับซ้อนในกรณีที่เลวร้ายที่สุดด้วย

Quicksortเป็นอัลกอริทึมแบบแบ่งและพิชิต (divide-and-conquer)ซึ่งอาศัย การดำเนินการ แบ่งส่วน : ในการแบ่งส่วนอาร์เรย์จะมีการเลือก องค์ประกอบที่เรียกว่า pivot ^{[ 25 ] [ 26 ]}องค์ประกอบทั้งหมดที่เล็กกว่า pivot จะถูกย้ายไปอยู่ข้างหน้า และองค์ประกอบทั้งหมดที่ใหญ่กว่าจะถูกย้ายไปอยู่ข้างหลัง ซึ่งสามารถทำได้อย่างมีประสิทธิภาพในเวลาเชิงเส้นและแบบ in-placeจากนั้นรายการย่อยที่เล็กกว่าและใหญ่กว่าจะถูกเรียงลำดับแบบเรียกซ้ำ ซึ่งให้ความซับซ้อนของเวลาโดยเฉลี่ย O( n log n ) โดยมีค่าใช้จ่ายน้อย ดังนั้นจึงเป็นอัลกอริทึมที่ได้รับความนิยม การใช้งาน quicksort ที่มีประสิทธิภาพ (ด้วยการแบ่งส่วนแบบ in-place) มักจะเป็นการเรียงลำดับที่ไม่เสถียรและค่อนข้างซับซ้อน แต่เป็นหนึ่งในอัลกอริทึมการเรียงลำดับที่เร็วที่สุดในทางปฏิบัติ เมื่อรวมกับการใช้พื้นที่ O(log n ) ที่ไม่มากนัก quicksort จึงเป็นหนึ่งในอัลกอริทึมการเรียงลำดับที่ได้รับความนิยมมากที่สุดและมีอยู่ในไลบรารีการเขียนโปรแกรมมาตรฐานหลายแห่ง

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

หากการรับประกันประสิทธิภาพ O( n log n ) เป็นสิ่งสำคัญ ก็มีการปรับเปลี่ยนง่ายๆ เพื่อให้ได้ผลลัพธ์นั้น แนวคิดนี้มาจาก Musser โดยการกำหนดขีดจำกัดความลึกสูงสุดของการเรียกซ้ำ^{[ 27 ]}หากเกินขีดจำกัดนั้น การเรียงลำดับจะดำเนินต่อไปโดยใช้อัลกอริธึม heapsort Musser เสนอว่าขีดจำกัดควรเป็นซึ่งประมาณสองเท่าของความลึกของการเรียกซ้ำสูงสุดที่คาดหวังโดยเฉลี่ยกับอาร์เรย์ที่เรียงลำดับแบบสุ่ม ${\displaystyle 1+2\lfloor \log _{2}(n)\rfloor }$

Shellsortถูกคิดค้นโดยDonald Shellในปี 1959 ^{[ 28 ]}มันปรับปรุงการเรียงลำดับแบบแทรกโดยการย้ายองค์ประกอบที่ไม่อยู่ในลำดับมากกว่าหนึ่งตำแหน่งในแต่ละครั้ง แนวคิดเบื้องหลัง Shellsort คือการเรียงลำดับแบบแทรกใช้ เวลา ⁠ ⁠${\displaystyle O(kn)}$โดยที่ k คือระยะทางที่มากที่สุดระหว่างองค์ประกอบที่ไม่อยู่ในตำแหน่งสองรายการ ซึ่งหมายความว่าโดยทั่วไปแล้วจะทำงานในเวลา O ( n ² ) แต่สำหรับข้อมูลที่เรียงลำดับแล้วเป็นส่วนใหญ่ โดยมีองค์ประกอบที่ไม่อยู่ในตำแหน่งเพียงไม่กี่รายการ มันจะทำงานได้เร็วกว่า ดังนั้น โดยการเรียงลำดับองค์ประกอบที่อยู่ห่างกันก่อน แล้วค่อยๆ ลดช่องว่างระหว่างองค์ประกอบที่จะเรียงลำดับ การเรียงลำดับขั้นสุดท้ายจึงคำนวณได้เร็วกว่ามาก การใช้งานอย่างหนึ่งสามารถอธิบายได้ว่าคือการจัดเรียงลำดับข้อมูลในอาร์เรย์สองมิติ แล้วเรียงลำดับคอลัมน์ของอาร์เรย์โดยใช้การเรียงลำดับแบบแทรก

ความซับซ้อนของเวลาในกรณีที่เลวร้ายที่สุดของ Shellsort ยังเป็นปัญหาที่ยังไม่มีคำตอบและขึ้นอยู่กับลำดับช่องว่างที่ใช้ โดยมีความซับซ้อนที่ทราบกันดีตั้งแต่O ( n² ⁾ถึงO ( n⁴ ^/³ ) และ Θ( n log ²ⁿ ) สิ่งนี้ประกอบกับข้อเท็จจริงที่ว่า Shellsort เป็น อัลกอริทึม แบบ in-placeต้องการโค้ดเพียงเล็กน้อย และไม่จำเป็นต้องใช้call stackทำให้มีประโยชน์ในสถานการณ์ที่หน่วยความจำมีจำกัด เช่น ในระบบฝังตัวและเคอร์เนลของระบบปฏิบัติการ

อัลกอริทึมการเรียงลำดับแบบบับเบิลซอร์ต และรูปแบบต่างๆ เช่นคอมบ์ซอร์ตและค็อกเทลซอร์ตเป็นอัลกอริทึมการเรียงลำดับที่เรียบง่ายแต่มีประสิทธิภาพต่ำมาก มักพบเห็นได้ในตำราเบื้องต้นเนื่องจากวิเคราะห์ได้ง่าย แต่ไม่ค่อยได้นำไปใช้ในทางปฏิบัติ

อัลกอริทึมการเรียง ลำดับแบบบับเบิลซอร์ตเป็นอัลกอริทึมการเรียงลำดับที่เรียบง่าย อัลกอริทึมจะเริ่มต้นที่จุดเริ่มต้นของชุดข้อมูล โดยจะเปรียบเทียบองค์ประกอบสองตัวแรก และหากตัวแรกมากกว่าตัวที่สอง ก็จะทำการสลับตำแหน่ง จากนั้นจะทำเช่นนี้ต่อไปสำหรับแต่ละคู่ขององค์ประกอบที่อยู่ติดกันจนถึงจุดสิ้นสุดของชุดข้อมูล จากนั้นจะเริ่มต้นใหม่อีกครั้งด้วยองค์ประกอบสองตัวแรก ทำซ้ำไปเรื่อยๆ จนกว่าจะไม่มีการสลับตำแหน่งเกิดขึ้นในรอบสุดท้าย^{[ 29 ]}เวลาเฉลี่ยและประสิทธิภาพในกรณีที่เลวร้ายที่สุดของอัลกอริทึมนี้คือ O( n ² ) ดังนั้นจึงไม่ค่อยได้ใช้ในการเรียงลำดับชุดข้อมูลขนาดใหญ่ที่ไม่มีลำดับ บับเบิลซอร์ตสามารถใช้ในการเรียงลำดับรายการจำนวนน้อย (ซึ่งประสิทธิภาพเชิงอะซิมโทติกไม่ถือเป็นโทษสูง) บับเบิลซอร์ตยังสามารถใช้ได้อย่างมีประสิทธิภาพกับรายการที่มีความยาวใดๆ ก็ได้ที่เกือบจะเรียงลำดับแล้ว (นั่นคือ องค์ประกอบไม่ได้อยู่นอกตำแหน่งอย่างมีนัยสำคัญ) ตัวอย่างเช่น หากมีองค์ประกอบจำนวนหนึ่งผิดตำแหน่งไปเพียงตำแหน่งเดียว (เช่น 0123546789 และ 1032547698) ฟังก์ชันการสลับตำแหน่งของบับเบิลซอร์ตจะจัดเรียงให้เข้าที่ในรอบแรก และในรอบที่สองจะจัดเรียงองค์ประกอบทั้งหมดให้เข้าที่ ดังนั้นการเรียงลำดับจะใช้เวลา เพียง 2ⁿ เท่านั้น

Comb sortเป็นอัลกอริธึมการเรียงลำดับที่ค่อนข้างง่ายซึ่งอิงตามbubble sortและได้รับการออกแบบครั้งแรกโดย Włodzimierz Dobosiewicz ในปี 1980 ^{[ 30 ]}ต่อมา Stephen Lacey และ Richard Box ได้ค้นพบและเผยแพร่อีกครั้งด้วย บทความ ในนิตยสารByteที่ตีพิมพ์ในเดือนเมษายน 1991 แนวคิดพื้นฐานคือการกำจัดค่าเต่าหรือค่าเล็กๆ ที่อยู่ใกล้ท้ายรายการ เนื่องจากใน bubble sort ค่าเหล่านี้จะทำให้การเรียงลำดับช้าลงอย่างมาก ( ค่า กระต่าย ซึ่งเป็นค่าขนาดใหญ่ที่อยู่รอบๆ ต้นรายการ ไม่ก่อให้เกิดปัญหาใน bubble sort) Comb sort ทำได้โดยการสลับองค์ประกอบที่อยู่ห่างกันในระยะทางที่กำหนดในอาร์เรย์ก่อน แทนที่จะสลับเฉพาะองค์ประกอบที่อยู่ติดกัน จากนั้นจึงลดระยะทางที่เลือกจนกระทั่งทำงานเหมือน bubble sort ปกติ ดังนั้น หาก Shellsort สามารถคิดได้ว่าเป็นเวอร์ชันทั่วไปของ insertion sort ที่สลับองค์ประกอบที่อยู่ห่างกันในระยะทางที่กำหนด Comb sort ก็สามารถคิดได้ว่าเป็นการนำ bubble sort มาใช้ในลักษณะเดียวกัน

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

การเรียงลำดับแบบนับ (Counting sort) ใช้ได้เมื่อทราบว่าข้อมูลนำเข้าแต่ละรายการอยู่ในเซตเฉพาะSของความเป็นไปได้ อัลกอริทึมนี้ทำงานในเวลา O(| S | + n ) และใช้หน่วยความจำ O(| S |) โดยที่nคือความยาวของข้อมูลนำเข้า หลักการทำงานคือการสร้างอาร์เรย์จำนวนเต็มขนาด | S | และใช้ ช่องที่ iในการนับจำนวนครั้งที่ สมาชิกที่ iของS ปรากฏ ในข้อมูลนำเข้า จากนั้นจะนับข้อมูลนำเข้าแต่ละรายการโดยการเพิ่มค่าในช่องที่เกี่ยวข้อง หลังจากนั้น จะวนลูปผ่านอาร์เรย์นับเพื่อจัดเรียงลำดับข้อมูลนำเข้าทั้งหมด อัลกอริทึมการเรียงลำดับนี้มักไม่สามารถใช้งานได้เนื่องจากSต้องมีขนาดเล็กพอสมควรเพื่อให้ประสิทธิภาพของอัลกอริทึมดีขึ้น แต่มีความเร็วสูงมากและแสดงพฤติกรรมเชิงเส้นกำกับที่ดีเยี่ยมเมื่อnเพิ่มขึ้น นอกจากนี้ยังสามารถปรับเปลี่ยนเพื่อให้มีพฤติกรรมที่เสถียรได้อีกด้วย

การเรียงลำดับ แบบ Bucket sort เป็นอัลกอริทึมการเรียง ลำดับแบบ แบ่งและพิชิต (divide-and-conquer) ที่ขยายแนวคิดของการเรียงลำดับแบบนับ (counting sort)โดยการแบ่งอาร์เรย์ออกเป็นกลุ่ม (buckets) จำนวนจำกัด จากนั้นแต่ละกลุ่มจะถูกเรียงลำดับแยกกัน โดยอาจใช้อัลกอริทึมการเรียงลำดับอื่น หรือใช้การเรียงลำดับแบบ Bucket sort ซ้ำๆ ก็ได้

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

อัลกอริ ทึม Radix sortเป็นอัลกอริทึมที่เรียงลำดับตัวเลขโดยการประมวลผลแต่ละหลัก ตัวเลข n ตัว ซึ่งแต่ละตัว ประกอบด้วยkหลัก จะถูกเรียงลำดับในเวลา O( n · k ) Radix sort สามารถประมวลผลหลักของแต่ละตัวเลขได้โดยเริ่มจากหลักที่มีค่าน้อยที่สุด (LSD) หรือเริ่มจากหลักที่มีค่ามากที่สุด (MSD) อัลกอริทึม LSD จะเรียงลำดับรายการตามหลักที่มีค่าน้อยที่สุดก่อน โดยรักษาระดับลำดับสัมพัทธ์โดยใช้การเรียงลำดับแบบเสถียร จากนั้นจึงเรียงลำดับตามหลักถัดไป และทำเช่นนี้ต่อไปเรื่อยๆ จากหลักที่มีค่าน้อยที่สุดไปยังหลักที่มีค่ามากที่สุด จนได้รายการที่เรียงลำดับแล้ว ในขณะที่ LSD radix sort จำเป็นต้องใช้การเรียงลำดับแบบเสถียร แต่ MSD radix sort ไม่จำเป็นต้องใช้ (เว้นแต่ต้องการการเรียงลำดับแบบเสถียร) การเรียงลำดับแบบ MSD radix sort แบบ in-place ไม่ใช่การเรียงลำดับแบบเสถียร โดยทั่วไปแล้ว อัลกอริทึม counting sortจะถูกใช้ภายในโดย radix sort วิธีการเรียงลำดับแบบ ผสมผสานเช่น การใช้insertion sortสำหรับ bin ขนาดเล็ก จะช่วยปรับปรุงประสิทธิภาพของ radix sort ได้อย่างมาก

ในAlgorithms and Data Structures Niklaus Wirthได้เปรียบเทียบเวลาการทำงานของอัลกอริธึมยอดนิยมหลายตัวบนคอมพิวเตอร์Lilith ^{[ 31 ]}

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

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

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

เทคนิคอีกอย่างหนึ่งในการเอาชนะปัญหาขนาดหน่วยความจำคือการใช้การเรียงลำดับภายนอกตัวอย่างเช่น วิธีหนึ่งคือการรวมอัลกอริทึมสองตัวเข้าด้วยกันในลักษณะที่ใช้ประโยชน์จากจุดแข็งของแต่ละตัวเพื่อปรับปรุงประสิทธิภาพโดยรวม ตัวอย่างเช่น อาร์เรย์อาจถูกแบ่งออกเป็นส่วนย่อยที่มีขนาดพอดีกับ RAM เนื้อหาของแต่ละส่วนย่อยจะถูกเรียงลำดับโดยใช้อัลกอริทึมที่มีประสิทธิภาพ (เช่นquicksort ) และผลลัพธ์จะถูกรวมเข้าด้วยกันโดยใช้ การรวมแบบ kทางที่คล้ายกับที่ใช้ในmerge sortวิธีนี้เร็วกว่าการทำ merge sort หรือ quicksort กับรายการทั้งหมด^{[ 33 ] [ 34 ]}

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

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

อัลกอริทึมการเรียงลำดับนั้นตรงกันข้ามกับอัลกอริทึมการสับเปลี่ยนโดยสิ้นเชิงทั้งสองแตกต่างกันอย่างมากเพราะต้องใช้แหล่งที่มาของตัวเลขสุ่ม การสับเปลี่ยนสามารถทำได้โดยใช้อัลกอริทึมการเรียงลำดับเช่นกัน นั่นคือการเรียงลำดับแบบสุ่ม: การกำหนดตัวเลขสุ่มให้กับแต่ละองค์ประกอบในรายการแล้วเรียงลำดับตามตัวเลขสุ่มเหล่านั้น อย่างไรก็ตาม โดยทั่วไปแล้ววิธีนี้ไม่นิยมใช้ในทางปฏิบัติ และมีอัลกอริทึมการสับเปลี่ยนที่เรียบง่ายและมีประสิทธิภาพที่เป็นที่รู้จักกันดี นั่นคือการสับเปลี่ยนแบบฟิชเชอร์ -เยตส์ ( Fisher–Yates shuffle )

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

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

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

• Knuth, Donald E. (1998), การเรียงลำดับและการค้นหา , ศิลปะแห่งการเขียนโปรแกรมคอมพิวเตอร์, เล่ม 3 (ฉบับที่ 2), บอสตัน: Addison-Wesley, ISBN 0-201-89685-0
• Sedgewick, Robert (1980), "การเรียงลำดับอย่างมีประสิทธิภาพด้วยคอมพิวเตอร์: บทนำ" , ความน่าจะเป็นเชิงคำนวณ , นิวยอร์ก: Academic Press, หน้า  101–130 , ISBN 0-12-394680-8

เว็บไซต์ Wikibook Algorithm implementationมีหน้าเว็บที่กล่าวถึงหัวข้อ: อัลกอริทึมการเรียงลำดับ

เว็บไซต์ Wikibook A-level Mathematicsมีหน้าหนึ่งที่กล่าวถึงหัวข้อ: อัลกอริทึมการเรียงลำดับ

วิกิมีเดียคอมมอนส์มีสื่อที่เกี่ยวข้องกับอัลกอริธึมการเรียงลำดับ

• ภาพเคลื่อนไหวแสดงขั้นตอนการเรียงลำดับในWayback Machine (เก็บถาวรเมื่อวันที่ 3 มีนาคม 2015)
• อัลกอริทึมการเรียงลำดับแบบลำดับและแบบขนาน – คำอธิบายและการวิเคราะห์อัลกอริทึมการเรียงลำดับหลายประเภท
• พจนานุกรมของอัลกอริทึม โครงสร้างข้อมูล และปัญหา – พจนานุกรมของอัลกอริทึม เทคนิค ฟังก์ชันทั่วไป และปัญหาต่างๆ
• มุมมองที่ค่อนข้างสงสัยเกี่ยวกับอัลกอริทึมการเรียงลำดับ – อภิปรายอัลกอริทึมคลาสสิกหลายตัวและเสนอทางเลือกอื่นนอกเหนือจากอัลกอริทึมควิกซอ ร์ต
• 15 อัลกอริทึมการเรียงลำดับใน 6 นาที (Youtube) – การนำเสนอภาพและเสียงของ 15 อัลกอริทึมการเรียงลำดับใน 6 นาที
• ลำดับ A036604 ในฐานข้อมูล OEIS ที่มีชื่อว่า "การเรียงลำดับตัวเลข: จำนวนการเปรียบเทียบขั้นต่ำที่จำเป็นในการเรียงลำดับองค์ประกอบ n รายการ" – ดำเนิน การโดยอัลกอริทึม Ford–Johnson
• อัลกอริทึมการเรียงลำดับที่ใช้ในภาพวาดชื่อดัง (ยูทูบ) – การแสดงภาพอัลกอริทึมการเรียงลำดับในภาพวาดชื่อดังหลายภาพ
• การเปรียบเทียบอัลกอริธึมการเรียงลำดับ – ดำเนินการทดสอบอัลกอริธึมการเรียงลำดับหลัก 9 แบบ โดยใช้ Python timeit และGoogle Colab