Split until each run has one element, then merge pairs of sorted runs by comparing their front values. Accumulate a merged run in tmp before copying it back.
A merge-sort simulator showing recursive splits and a temporary merge array
Play, step, or seek with the slider. The lower row is the temporary array tmp.
Merging compares the front values
Both runs are sorted, so the smaller front value is the next overall minimum. Merging takes time proportional to their combined lengths. There are O(log n) levels with O(n) merging work per level, for O(n log n) time even in the worst case.
When equal, the left value is chosen first (a[i] <= a[j]), preserving stability. Changing the comparison to < breaks this property.
Coding exercises: count inversions
When the next right-hand value is smaller, every remaining value in the left run is larger. Add mid − i + 1 to the inversion count at that step. The total is computed in O(n log n).
else: # right value is smaller
inv += mid - i + 1 # remaining left values exceed a[j]
tmp.append(a[j]); j += 1