How to Implement Merge Sort

Merge Sort works by repeatedly splitting the array in half until each piece has only one element. A single element is already sorted by definition. Then it merges those sorted pieces back together in the correct order.

Calculate the middle index of the current array segment. Recursively call Merge Sort on the left half from the start to the middle. Recursively call Merge Sort on the right half from the middle plus one to the end. These calls keep splitting until the base case is reached.

The base case is when the segment has one or zero elements, meaning the start index is greater than or equal to the end index. At this point, simply return because a single element needs no sorting.

The Merge function takes two sorted halves and combines them into a single sorted segment. Create a temporary array to hold the merged result. Use two pointers, one starting at the beginning of the left half and one starting at the beginning of the right half.

In a loop, compare the elements that the two pointers are currently pointing at. Take the smaller element and place it into the temporary array. Advance the pointer of whichever half you just took from. Continue until one of the halves is completely exhausted.

After the loop, one half may still have remaining elements. Copy all remaining elements from the left half into the temporary array, then copy all remaining elements from the right half. These elements are already in sorted order so no comparison is needed.

Once the temporary array is fully built, copy all its elements back into the corresponding positions of the original array. The segment is now sorted in place and the recursion can unwind to merge larger and larger sorted pieces.