Quicksort

Kerugian dari versi sederhana diatas membutuhkan ruang simpan O("n") yang lebih besar, yang sama buruknya seperti merge sort. Memory tambahan yang dibutuhkan dapat juga secara radikal berpengaruh pada kecepatan dan performa cache pada implementasi praktiknya. Terdapat juga versi yang lebih rumit yang menggunakan algoritme partisi in-place dan dapat mencapai urutan lengkap menggunakan ruang O(log"n") (tidak dihitung input) pada rata-rata (untuk sekali pemanggilan tumpukan). Kita mulai dengan fungsi partisi: