Samsorteringsalgorithm för listor - varför är varje körning O(n)?

Hej!

Har en fråga om facit i nedanstående uppgift

Facit:

Jag har markerat frågan jag har genom att stryka under den relevanta delen i facit. Hur kan vi vara så säker på att listan sorteras i $O(n)$ tid? Generellt brukar väl inte sorteringsalgorithmer för listor vara så bra som $O(n)$...?

Som jag tolkar frågan, så är de $k$ stycken listorna redan sorterade (var för sig) från början. Man ska inte sortera varje lista.

Man ska "bara" slå ihop (merge) dessa listor så att man får en lång sorterad lista med $\cancel{k\cdot n}$ $n$ element.

Edit: Ursprungligen hade jag för mig att varje lista innehåller $n$ element, men det är totalt $n$ element i alla listor ihop enligt uppgiftens frågeställning

Svara