Működése hasonló ahhoz, mint amikor lapjainkat rendezzük egy kártyajáték során. A rendezetlen pakliból elvesszük a felső lapot és beszúrjuk a rendezett lapok közé.

A beszúró rendezés hatékony algoritmus kisszámú elem rendezésére. Sok esetben a leggyorsabb négyzetes rendezés. A rendezendő számokat kulcsoknak is szokás nevezni. A beszúró rendezés stabil rendezés, azaz az azonos kulcsú elemek egymáshoz viszonyított sorrendjét megőrzi. Például, ha van kettő 32-es, akkor azok ugyanabban a sorrendben lesznek a rendezés után, mint ahogyan rendezés előtt voltak. Ez azért van, mert jobbról balra keresi meg az elem helyét, és a vele egyenlőket már nem lépi át.

A bemenő kulcsokat helyben rendezi, tehát a számokat az $A$ tömbön belül rakja a helyes sorrendbe és legfeljebb csak állandó számú elem tárolódik a tömbön kívül.

Az algoritmus az összehasonlító rendezések közé tartozik, azaz az elemek sorrendjét azok összehasonlításával állapítja meg.

A beszúró rendezés egyik előnye az, hogy nem csak tömbben tárolt elemek rendezésére alkalmas, hanem a láncolt listákra is könnyen alkalmazható. A láncolt megvalósítás futási ideje közel azonos a tömbös megvalósítás futási idejével.

Működése:

A bemenet számok $n$ elemű $(a_1, a_2, ..., a_n)$ sorozata, a kimenet pedig az $a_1, a_2, ..., a_n$ számok egy olyan $(a_1', a_2', ..., a_n')$ átrendezése, ahol $a_1' \leq a_2' \leq ... \leq a_n'$.

A tömbünket két résztömbként kezeljük, a már rendezettek és a rendezésre váró kulcsok résztömbjeként. Kezdetben a rendezettek résztömbjében az első elem van benne. Ezután a rendezetlen kulcsok résztömbjének első elemét szúrjuk be a megfelelő helyre a rendezettek résztömbjébe. Ehhez kimentjük ezt az elemet egy $x$ változóba és a nála nagyobb elemeket jobbrább „toljuk”. $(n-1)$ beszúrás után egy monoton növekvően rendezett tömböt kapunk.

Az algoritmus egy külső és egy belső ciklusból áll. A külső ciklus beszúrásonként lép egyet és addig halad, amíg minden elemet be nem szúrtuk a helyére. A belső ciklus a beszúrás közbeni jobbra másolásokért felelős és addig halad, amíg meg nem találtuk az aktuálisan beszúrandó elem helyét.

Minden beszúrás annyi inverziót szűntet meg, ahány elemet jobbra toltunk, és nem hoz létre új inverziót. (Inverzió: a nagyobb értékű elem megelőzi a kisebb értékűt). Ez a tulajdonság különösen gyorssá teszi a beszúró rendezést abban az esetben, ha a tömb „nagyjából rendezett” volt.

Műveletigény:

A felhasznált idő a bemenettől függ. Két azonos méretű tömböt is rendezhet különböző idők alatt. Ez nagyban függ a bemenet rendezettségétől.

• $MT(n) \in \Theta(n^2)$, ami akkor lehetséges, ha minden egyes alkalommal belépünk a belső ciklusba, azaz a tömbünk fordítottan rendezett.
• $AT(n) \in \Theta(n^2)$
• $mT(n) \in \Theta(n)$, ami akkor lehetséges, ha a belső ciklusba soha nem lépünk be, azaz a tömb alapból rendezve van.

Gyakorlati alkalmazása:

A vegyes rendezésben szokták használni, ahol összekombinálják a beszúró rendezést egy gyors rendezéssel (merge sort, quicksort, heap sort). Ha kevés elemet kell rendezni, akkor a beszúró rendezés fut le, ha sok elemet kell rendezni, akkor a gyors rendezést használja a vegyes rendezés.