Задача: Улучшение быстрой сортировки
Псевдокод: Быстрая сортировка, оптимизация №2 (qsort4)
  1. void qsort4(l, u)
  2. if u - l < cutoff
  3. return
  4.  
  5. swap(l, randint(l, u))
  6. t = x[l]
  7. i = l
  8. j = u+1
  9. while (1)
  10. /* пропуск элементов справа и слева,
  11. чтобы не делать лишней работы */
  12. do i++ while i <= u && x[i] < t
  13. do j-- while x[j] > t
  14.  
  15. if i > j
  16. break;
  17. tmp = x[i] x[i] = x[j] x[j] = tmp
  18.  
  19. swap(l, j)
  20.  
  21. qsort4(l, j-1)
  22. qsort4(j+1, u)
  23.  
  24. /* При этом вызов всей процедуры сортировки
  25. в программе будет иметь вид: */
  26. qsort4(0, n-1);
  27. isort3();