by Jonathan Speek on Sorting, Python, cs

Merge Sort

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):

merge sort

Python: