Merge Sort is an algorithm used to sort an array or list that is considered to have a complexity O(n log n). Merge sort takes advantage of a recursive, divide-and-conquer method that helps it break the O(n²) barrier.
How it Works:
Merge sort begins by finding the middle position of a list and recursively sorts its left and right sublists (divide and conquer). It then merges the two sorted sublists back into a single sorted list. It stops the process when sublists can no longer be subdivided (the list is now considered sorted).
Below is a nice gif that shows this process (See my Python implementation at bottom):