In situ versus ex situ

Lateinisch „in situ“ (oder angelsächsisch „in place“) heißt am selben Platze, an Ort und Stelle, und bedeutet, daß die Menge dort, wo sie sich befindet, auch sortiert wird. Im Computer wäre das demnach derselbe Speicherbereich. Nur ein konstant großer Speicherbereich, in extremer und Reinform nur ein Speicherplatz mehr ist für die nötigen Tauschvorgänge vonnöten und zulässig. Es liegt auf der Hand, daß einem solchen Sortieren ein gewisser Engpaß anhaftet und es ggf. auch langsamer vonstatten geht, als wenn mehr zusätzliche Speicherplätze bereitstünden, die das Sortieren flexibler gestalten könnten. Dafür ist der Bedarf an zusätzlichem Speicher jedoch minimal.

Der Gegensatz dazu ist „ex situ“ bzw. „out of place“. Bei ausreichend zusätzlichem Speicher kann die Sortiermenge während des Sortierens sogar komplett im Speicher verschoben werden, so bei AVL-, B-, Binary-Search-Tree-, Fibonacci-, Merge-, Patience-, Red-Black-, Skip-, Splay-, Tree- und Trisort (eine stabile Variante des Quicksorts).

Eine genaue Definition und Unterscheidungsmöglichkeit beider Vorgehensweise fand ich bis heute nicht. Aus meiner Sicht ist ein Algorithmus dann nicht mehr ex situ, sondern in situ, wenn er mit so wenig Speicher auskommen muß, daß sich Tauschvorgänge nicht vermeiden lassen, währendhingegen bei ausreichendem Speicher ausschließlich Verschiebungen möglich sind. Ganz so allgemeingültig ist das aber nicht, da z.B. Bubble- und Insertionsort ohne großen Änderungsaufwand und mit demselben Speicherbedarf (mit nur einem zusätzlichen Speicherplatz!) sowohl auf der Basis von Verschiebungen als auch Vertauschungen realisiert werden können.