Sammanfoga sortering är en sorteringsalgoritm som fungerar genom att rekursivt dela upp en array i mindre och mindre subarrayer tills varje subarray bara innehåller ett element. Subarrayerna slås sedan samman i sorterad ordning, med början med de minsta subarrayerna och fram till den största subarrayen.
Här är ett exempel på hur sammanslagningssortering fungerar. Låt oss börja med följande array:
```
[5, 3, 1, 2, 4]
```
Vi delar först upp arrayen i två underarrayer:
```
[5, 3]
[1, 2, 4]
```
Vi sorterar sedan rekursivt varje subarray. Den första subarrayen är redan sorterad, så vi behöver inte göra någonting. Den andra subarrayen kan sorteras genom att rekursivt dela upp den i ytterligare två subarrayer, och så vidare.
När underarrayerna är sorterade kan vi slå samman dem i sorterad ordning. Vi börjar med att jämföra de första elementen i varje subarray. Det mindre elementet läggs till i den sorterade arrayen och det andra elementet kasseras. Vi fortsätter denna process tills alla element i båda subarrayerna har lagts till i den sorterade arrayen.
```
[1, 2, 3, 4, 5]
```
Det sista steget är att returnera den sorterade arrayen.
Merge sort har ett antal fördelar jämfört med andra sorteringsalgoritmer. Det är garanterat att producera en sorterad array i O(n log n) tid, oavsett den initiala ordningen för elementen i arrayen. Dessutom är merge sort stabil, vilket innebär att element som är lika kommer att visas i den sorterade arrayen i samma ordning som de dök upp i den ursprungliga arrayen.
Här är en mer detaljerad förklaring av sammanslagningssorteringsalgoritmen:
1. Dela upp arrayen i två subarrayer med ungefär lika längd.
2. Sortera varje subarray rekursivt.
3. Slå samman de två sorterade subarrayerna till en enda sorterad array.
Sammanfogningssteget är nyckeln till sammanslagningssortering. Det är viktigt att slå samman subarrayerna i sorterad ordning. Detta kan göras genom att jämföra de första elementen i varje subarray och lägga till det mindre elementet till den sorterade arrayen. Det andra elementet kasseras. Denna process upprepas tills alla element i båda subarrayerna har lagts till i den sorterade arrayen.
Merge sort är en kraftfull sorteringsalgoritm som garanterat producerar en sorterad array i O(n log n) tid. Den är också stabil, vilket gör den lämplig för att sortera data som innehåller lika stora element.
