Explain merge sort and its advantages.

Merge sort is a divide-and-conquer algorithm that recursively divides the array into halves until single elements, then merges them back in sorted order. Time complexity is O(n log n) for all cases - consistent performance. Space is O(n) for the merge operation. Advantages: stable sort, predictable performance, parallelizable, works well for linked lists (no random access needed). Disadvantage: requires extra space unlike in-place sorts.