Merge sort and the complexities compared

Merge sort applies a very powerful strategy: « divide and conquer ». We cut the array into two halves, we sort each half recursively (so in the same way, cutting it again into two), then we merge the two sorted halves into a single sorted list. Merging two already-sorted lists is fast: we simply compare their first remaining elements and take the smaller one each time.

Merge tree on [6, 3, 8, 2]:

level 0 (division) :           [6, 3, 8, 2]
                               /            \
level 1 (division) :      [6, 3]           [8, 2]
                          /     \           /     \
level 2 (base)   :     [6]     [3]       [8]     [2]

going back up (merge) :
level 1 (merge) :       [3, 6]             [2, 8]
level 0 (merge) :              [2, 3, 6, 8]

At each level of the tree, merging all the pairs costs in total O(n) comparisons (each element is looked at once). Now there are about log2(n) levels, since we halve the size at each stage. The total cost is therefore O(n log n): much better than O(n²) when n grows large.

def fusion(gauche, droite):
    resultat = []
    i = j = 0
    while i < len(gauche) and j < len(droite):
        if gauche[i] <= droite[j]:
            resultat.append(gauche[i]); i += 1
        else:
            resultat.append(droite[j]); j += 1
    resultat.extend(gauche[i:])
    resultat.extend(droite[j:])
    return resultat

def tri_fusion(a):
    if len(a) <= 1:
        return a
    milieu = len(a) // 2
    gauche = tri_fusion(a[:milieu])
    droite = tri_fusion(a[milieu:])
    return fusion(gauche, droite)

Comparison of complexities (n = size of the array):

selection : O(n^2)   (always, even if already sorted)
insertion : O(n^2) worst case, O(n) best case (nearly sorted)
bubble    : O(n^2) worst case, O(n) best case (with the stop flag)
merge     : O(n log n) always (but uses extra memory)

Classic pitfall: believing that merge sort is always the best choice — it uses more memory (the temporary sublists) than an in-place sort such as bubble sort or insertion sort.