Merge sort

Merge sort is a divide-and-conquer algorithm that divides the input array into two halves, recursively sorts them, and then merges the sorted halves to produce a sorted output.

Time complexity: O(n log n) in all cases (best, average, worst).

Space complexity: O(n) due to the auxiliary array needed for merging.

Merge sort is a stable sorting algorithm, meaning it preserves the relative order of equal elements.

Color code:

• Blue: Left subarray being merged
• Green: Right subarray being merged
• Red: Elements being compared
• Purple: Position being written to