ภาษา Go เตรียมเปลี่ยนฟังก์ชั่น sort จากเดิมใช้ QuickSort มาเป็น pdqsort หรือ pattern-defeating quicksort อัลกอริทึมเรียงลำดับที่ประสิทธิภาพโดยรวมดีขึ้นมากในหลายกรณี แม้ว่ากรณีที่แย่ที่สุดยังเป็น O(n log n) เช่นเดิมก็ตาม

pdqsort พัฒนาโดย Orson R. L. Peters จากมหาวิทยาลัย Leiden ในเนธอร์แลนด์เมื่อปี 2017 มีจุดได้เปรียบสำคัญคือยิ่งค่าที่เป็นไปได้ของข้อมูลมีน้อยแม้จำนวนข้อมูลจะมีจำนวนมาก เช่น เรียงเลขนับล้านตัว แต่มีเลขที่เป็นไปได้เพียง 0 ถึง 9 ในกรณีเช่นนี้ pdqsort จะมีประสิทธิภาพสูงมาก และหากโค้ดสำหรับเปรียบเทียบค่าไม่ต้องมี branch ประสิทธิภาพในการรันอัลกอริทึมก็จะสูงขึ้นมาก

ภาษา Rust นั้นใช้ pdqsort มาตั้งแต่ปี 2017 หลังอัลกอริทึมนี้ถูกเสนอมาไม่นาน เป็นฟังก์ชั่น sort_unstable ส่วนภาษา Go นั้นมีการเสนอให้เปลี่ยนมาตั้งแต่ปลายปีที่แล้วและกำลังอยู่ระหว่างรีวิว หากไม่มีปัญหาอะไรก็น่าจะได้ใช้ในเวอร์ชั่นต่อไป

ที่มา - golang/go