## Using Merge Sort

Although the quicksort on average is pretty fast, it still has the theoretical worst time complexity of *O(n²)*. In this section, we shall examine another sorting algorithm, called **merge sort**, in which the worst time complexity is *O(n log n)*. Similar to quick sort, merge sort belongs to the divide and conquer class of algorithms.

Merge sort can be summarized in three simple steps as follows:

- Split the array in the middle
- Recursively sort each part separately
- Merge the two sorted parts together

In the following section, we will develop the preceding steps gradually, at each turn slowly building our understanding of how merge sorting works.

### Note

Although merge sort is theoretically faster than quick sort, in practice, some implementations of quick sort can be more efficient than merge sort. Additionally, the merge sort uses about*O(n)*memory as opposed to quick sort, which is*O(log n)*.

### Dividing the Problem

In the preceding section, we saw how we can use a recursive technique to split the...