Az első feladathoz hasonlóan ismét adott egy lista, melyben n darab pozitív egész szám található, rendezetlenül. A célunk, hogy a lista elemeit növekvő sorrendbe rendezzük (feltételezhetjük, hogy a lista minden eleme különböző).

A rendezésünk ezúttal a következő elven működik: Az első számot egyelemű rendezett listának tekintjük, a vizsgálódást a 2. számmal kezdjük. Fogjuk a már rendezett listát (vagyis az újonnan bevett számtól balra lévő elemeket), összehasonlításokat végzünk, és beszúrjuk a megfelelő helyre az új számot.

Az összehasonlításokra kétféle különböző algoritmust használunk.
1. Az első esetben a már rendezett listán elindulunk az első elemtől, és megnézzük, hogy az újonnan bevett szám kisebb-e, mint a listában lévő aktuális elem. Amennyiben igen, úgy az adott szám elé beszúrjuk az új elemet, majd jön a következő elem.
Amennyiben nem, úgy megpróbáljuk összehasonlítani az újonnan bevett számot a rendezett lista következő elemével.
Amennyiben végigérünk a listán, a lista végére szúrjuk be az új elemet.

2. A második esetben fogjuk a már rendezett listának a középső elemét. Páros elemszámú listánál az elméleti középső elemtől balra lévő számot tekintjük középsőnek (4 elemnél például a másodikat). Ezt összehasonlítjuk az újonnan bevezetett elemmel. Amennyiben a szám kisebb, úgy csak a már rendezett lista középső elemétől balra elhelyezkedő rész-listájával dolgozunk, amennyiben a szám nagyobb, úgy a rendezett lista középső elemétől jobbra elhelyezkedő rész-listával. Addig haladunk, amíg ez a rész-lista nem lesz üres, ekkor az utolsóként vizsgált középső elem bal vagy jobb szomszédjaként beszúrjuk az elemet.

A legjobb és legrosszabb esetekben hány összehasonlítást kell elvégeznünk az n elemű lista rendezéséhez az első és a második esetben? (2 és 8 pont)