Es ist mir nicht nur um die zeitliche Komplexität gegangen. Ob die zeitliche Komplexität überhaupt von der Komplexität der Vergleiche bestimmt wird, ist außerdem gar nicht von vornherein klar. Bei den in den Beispielen verwendeten einfachen Integervergleichen wird etwa in aller Regel der Aufwand für die Kopien und Kontrollstrukturen überwiegen, auch in der normalen Inplace-Implementation.