Merge Sort
Learn Merge Sort (Sorting, Data Structures & Algorithms) with worked examples, diagrams and interview questions. Free on JavaSchoolLab.
Merge Sort - O(n log n), Divide and Conquer Recursively splits the array in half until each piece has one element (trivially sorted), then MERGES sorted halves back together. Guaranteed O(n log n) in every case - best, average, and worst - unlike Quick Sort's O(n²) worst case. Stable - the merge step takes from the left half whenever values are equal, preserving original order. Not in-place - needs O(n) auxiliary space for the merge step's temporary array.