Flettesortering

Fra Wikipedia, den frie encyklopedi

Flettesortering (en. merge sort) er en sorteringsalgoritme som baserer seg på fletting av to og to lister.

Det første algoritmen må gjøre er å dele hele listen i to tilnærmet like store lister. Deretter deler den disse igjen i to tilnærmet like store lister, helt til den står igjen med 2 tall i hver delmengde.

Deretter tar den for seg hver delmengde, sorterer disse (f.eks med bruk av Boblesortering), fletter disse sammen med andre sorterte delmengder, helt til man står igjen med en sortert liste.

Eksempel:

Vi skal sortere listen: 8 3 9 13 12 2 14 10 5

1. steg: Deler tallene rundt midten: (8 3 9 13) || (12 2 14 10 5)

2. steg: Fortsetter å dele: (8 3) || (9 13) || (12 2) || (14 10 5)

3. steg: Sorterer hver delmengde: (3 8) || (9 13) || (2 12) || (5 10 14)

4. steg: Fletter sammen to og to delmengder: (3 8 9 13) || (2 5 10 12 14)

5. Etter siste fletting er listen ferdig sortert: 2 3 5 8 9 10 12 13 14