การเรียงลำดับสปาเก็ตตี้เป็นอัลกอริธึมแบบอนาล็อกที่ใช้เวลาเชิงเส้นสำหรับการเรียงลำดับรายการ ซึ่งแนะนำโดยAK Dewdneyในคอลัมน์Scientific American ของเขา ^{[ 1 ] [ 2 ] [ 3 ]}อัลกอริธึมนี้เรียงลำดับรายการที่ต้องการ พื้นที่สแต็ก O ( n ) อย่างเสถียร ต้องใช้โปรเซสเซอร์แบบขนาน ซึ่งถือว่าสามารถค้นหาค่าสูงสุดของลำดับรายการได้ในเวลา O ( 1 )

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

1. สำหรับแต่ละจำนวนxในรายการ ให้หาแท่งที่มีความยาวx (วิธีปฏิบัติอย่างหนึ่งในการเลือกหน่วยคือ ให้จำนวนที่มากที่สุดในรายการm แทนแท่งสปาเก็ตตี้หนึ่งแท่ง ในกรณีนี้ แท่งสปาเก็ตตี้หนึ่งแท่งจะเท่ากับสปาเก็ตตี้ mหน่วย เพื่อให้ได้แท่งที่มีความยาวxให้หักแท่งสปาเก็ตตี้ออกเป็นสองส่วน โดยส่วนหนึ่งมีความยาวxหน่วย แล้วทิ้งอีกส่วนหนึ่งไป)
2. เมื่อคุณรวบรวมแท่งสปาเก็ตตี้ได้ครบแล้ว ให้กำแท่งสปาเก็ตตี้เหล่านั้นหลวมๆ ไว้ในมือ แล้ววางลงบนโต๊ะให้ตั้งตรง โดยวางอยู่บนพื้นโต๊ะ จากนั้น สำหรับแต่ละแท่ง ให้ใช้มืออีกข้างหนึ่งค่อยๆ หย่อนลงมาจากด้านบนจนกระทั่งมาบรรจบกับแท่งสปาเก็ตตี้แท่งใดแท่งหนึ่ง ซึ่งเห็นได้ชัดว่าเป็นแท่งที่ยาวที่สุด นำแท่งนั้นออกแล้วเสียบเข้าไปที่ด้านหน้าของรายการเอาต์พุต (ซึ่งตอนแรกยังว่างอยู่) (หรืออีกนัยหนึ่งคือ วางไว้ในช่องว่างสุดท้ายที่ไม่ได้ใช้ของอาร์เรย์เอาต์พุต) ทำซ้ำจนกว่าจะนำแท่งสปาเก็ตตี้ออกหมดทุกแท่ง

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

• หน้าแรกของ AK Dewdney
• การนำแบบจำลองการคัดแยกทางกายภาพไปใช้ ศูนย์วิจัยสารสนเทศบูล
• การคำนวณแบบคลาสสิก/ควอนตัม สถาบัน IFF เก็บถาวรเมื่อ 19 กรกฎาคม 2011 ที่Wayback Machine