# Fusion sort

The usual dumb algorithms for sorting things require a number of operations proportional to the square of the number of elements to sort (O(n2)). In practice, the used algorithms require a number of operations proportional to n×log n.

The first one is the fusion sort.

The main point is that given two sorted list of numbers, generating the sorted merged list needs a number of operations proportional to the size of this result list. Two index indicate the next elements to take from each list, and one indicates where to store the smallest of the two (see figure 7.3). This process can be iterated, starting with packets of size 1 (which are already sorted ...) and merging them each time two by two (see figure 7.4). After k iterations of that procedure, the packets are of size 2k, so the number of iterations for this process is log2 n where n is the total number of objects to sort.

Each step of this main process cost the sum of the sizes of the resulting packets, which is n. Finally the total number of operations is Plog 2 n i=1 n = n × log2 n.