Két tömb összefésülése?

A Quicksort hű a nevéhez, ugyanis általánosságban egy igen gyors rendezőalgoritmusról beszélünk, igazából általános célra ez tekinthető az egyik leggyorsabbnak. A működése a következőképp zajlik:

A quicksort rekurzív, tehát a futása során többször meghívja saját magát.

Az eljárás megkap egy bal és egy jobb indexet (az első híváskor ez a rendezni való tömb első, és utolsó elemének indexe). Ezután kiválaszt egy ún. pivot elemet a bal és jobb index által határolt intervallumon, jelen esetben ez a bal és jobb index között középen levő elem. Az algoritmus innentől a következőképpen zajlik. Elindít a bal indextől egy változót jobbra, amit addig léptet, amíg az adott indexen levő érték nem lesz nagyobb vagy egyenlő a pivot elemmel. Eztán elindít jobboldalról is egy változót, amit addig léptet, amíg nem lesz az adott indexen levő elem kisebb, mint a pivot elem. Tehát megtalálja az első elemet balról, ami nagyobb, mint a középső elem, és az elsőt jobbról, ami kisebb. Ha ez megvan, kicseréli a két elemet, és lépteti tovább a változókat, amíg nem találnak ismét egy-egy nagyobb illetve kisebb elemet. Addig megy ez, amíg a két változó össze nem ér. Ezután elmondhatjuk, hogy a pivot elem baloldalán csak nála kisebb elemek vannak, a jobb oldalán pedig csak nála nagyobbak. A pivot elem tehát már a megfelelő helyen van, és a két oldalán keletkezik két "al-tömb", amik még nincsenek sorba rendezve, de kizárólag a pivotnál nagyobb, illetve kisebb elemeket tartalmazzák Ezen a ponton kétszer újrahívja önmagát a quicksort, egyszer úgy, hogy bal és jobb paraméterül a jelenlegi bal indexet, és a jobbról balra futtatott változó pozicióját adja be (tehát az intervallum a pivottól balra eső rész lesz), és egyszer úgy, hogy a jobb indexet, és a balról futtatott változó pozicióját adja be (ez pedig a pivottól jobbra eső rész lesz), és a fenti algoritmus alapján azokat is rendezi, és egész addig újrahívja magát egyre szűkebb intervallumokon, amíg össze nem ér a bal és jobboldala, és akkor a teljes tömb rendezve lesz.

A legtöbb quicksort algoritmus amit találok egy kicsit eltérően működik, ott a pivotelem az egyik szélső elem, és nem kétoldalról futtatja a változókat, hanem egy irányba jár végig, de a lényegi működése ugyanaz kb.

Itt egy interaktív példa az utóbbira, elég szemléletes:

[link]

A szakmabeli tudja kb hogy működik a Quicksort, de igazából fölösleges pontról pontra ismerni, mert

1. Elég ritkán kell neki leimplementálnia, mivel jóformán minden nyelvben talál beépített rendezéseket, amik már amúgyis szarrá vannak optimalizálva

2. Ha netalántán mégis meg kell írni, akkor fél perc alatt meg tudja nézni a pontos algoritmust, nem kell fejből írnia.