| Het sorteren van een gekoppelde lijst kan worden gedaan met behulp van verschillende algoritmen. Een veel voorkomende benadering is het gebruik van samenvoegsortering. Samenvoegsortering volgt een verdeel-en-heers-strategie:
1. Verdeel de lijst:
- Als de lijst één of nul knooppunten bevat, wordt deze als reeds gesorteerd beschouwd.
- Verdeel anders de lijst in twee ongeveer gelijke helften.
2. Veroveren (sorteer de sublijsten):
- Pas het samenvoeg-sorteeralgoritme recursief toe op beide helften van de lijst, waardoor ze effectief worden gesorteerd.
3. De gesorteerde sublijsten samenvoegen:
- Begin met twee verwijzingen, waarvan er één naar de kop van elke gesorteerde sublijst wijst.
- Vergelijk de gegevens in de knooppunten die door deze wijzers worden aangewezen om te bepalen welk element als eerste komt in de gesorteerde volgorde.
- Voeg het kleinere element toe aan een nieuwe lijst die wordt samengesteld.
- Verplaats de overeenkomstige aanwijzer naar het volgende knooppunt in de sublijst.
4. Herhaal stap 3:
- Ga door met het vergelijken en samenvoegen van elementen uit beide sublijsten, en verplaats indien nodig de aanwijzers.
- Herhaal dit proces totdat alle elementen uit beide sublijsten zijn samengevoegd in de nieuwe lijst.
5. Retourneer de samengevoegde gesorteerde lijst:
- Zodra alle elementen zijn samengevoegd, vertegenwoordigt de resulterende nieuwe lijst de gesorteerde gekoppelde lijst. Retourneer deze gesorteerde lijst als het definitieve antwoord.
Door de lijst systematisch in kleinere delen te verdelen, te sorteren en weer samen te voegen, sorteert merge sort effectief de gehele gekoppelde lijst in oplopende volgorde. De tijdscomplexiteit van deze benadering is O(n log n), waarbij n het aantal knooppunten in de gekoppelde lijst is. |
