Introduction to merge sort

Merge sort is one of the most efficient and widely used sorting algorithms. It is a general-purpose comparison-based sort that uses a divide-and-conquer approach under the hood (the input is recursively split into smaller pieces that are solved independently and then combined). It works by recursively dividing the input list into smaller sublists, sorting each, and merging them to produce a single list.

Example

Continuing from the earlier quicksort example, imagine you are a librarian tasked with organising a large collection of books in alphabetical order by title.