The Algorithm Design Manual (3rd) Exercise Solution 'E4-31'

Introduction

This series is my solutions for algorithm exercises in'The Algorithm Design Manual' 3rd edition.
It's my solutions, not model answers, so if you find some mistakes or more sophisticated solutions, please post in comment area below.

Repository

Here

Exercise 4-31

Question

Stable sorting algorithms leave equal-key items in the same relative order as in the original permutation. Explain what must be done to ensure that mergesort is a stable sorting algorithm.

Solution

The requirement of the stability is that when merging two arrays, of two elements with the same value, the element from the left (lower indices) array takes precedence over the ones from the right (higher indices).