How could we show that the algorithm of
- Mergesort is stable,
- Quicksort is not stable but it can be implemented as stable,
- Heapsort is not stable.
I have show that the algorithm of Insertion Sort is stable by showing the following invariant:
At the beginning of each iteration of the for loop, if $A[a]=A[b], a<b \leq j-1$, then $A[a]$ originally appeared before $A[b]$.
Do I have to show the same invariant for the algorithm of Mergesort??
Or do I have to show that it is stable in an other way??
$$$$
EDIT:
Could you give me some hints how the statement of the invariant for the Mergesort will look like??
Here is the proof that Mergesort is stable. I apologize for the clumsiness of the proof, as I spent a long time figuring out the indices and the boundaries.
Assume there are $n$ numbers in the array $A$ to be sorted. The numbers are in $A[0 ... n-1]$. To simplify matters, assume $n$ is $2^k$ for some positive integer number $k$. So there will be $k$ stages of merging. Let's call the stages from $1$ to $k$.
Notice that during stage $i$ of the merge sort, the numbers will be divided into $n / 2^{i-1}$ lists, denoted by $L_0, L_1, ... L_{k-1}$, where $k = n / 2^{i-1}$. List $L_j$ will be merged with $L_{j+1}$ for all even $j \lt k$. Also notice that a number originally at $A[x]$ will be moved to another place $A[y]$. According to the merge sort algorithm, $\lfloor x / 2^{i} \rfloor \times 2^{i} \le y \lt (\lfloor x / 2^{i} \rfloor +1)\times 2^{i}$.
Now, assume that on any stage $i$ ($1 \le i \le k$), the two identical numbers are positioned at array index $a$ and $b$ before merging, where $0 \le a \lt b \le n-1$. After the stage $i$'s merge, these two numbers will be moved to array index $y_a$ and $y_b$ respectively. We shall prove that $y_a < y_b$.
There are $3$ cases:
Case $1$: The two identical numbers positioned at $A[a]$ and $A[b]$ are in two different lists, and they are not being compared in stage $i$.
In such case, $\lfloor a/2^i \rfloor $ < $\lfloor b/2^i \rfloor $. According to the above, after the merge in stage $i$, $y_a$ is the new position of $A[a]$, and $y_b$ is the new position of $A[b]$. Then we have:
$\lfloor a/2^{i} \rfloor \times 2^{i} \le y_a \lt (\lfloor a/2^{i} \rfloor +1) \times 2^{i}$
$\lfloor b/2^{i} \rfloor \times 2^{i} \le y_b \lt (\lfloor b/2^{i} \rfloor +1) \times 2^{i}$
Note that $\lfloor a/2^i \rfloor \lt \lfloor b/2^i \rfloor \rightarrow \lfloor a/2^i \rfloor + 1 \le \lfloor b/2^i \rfloor \rightarrow (\lfloor a/2^i \rfloor + 1) \times 2^i \le (\lfloor b/2^i \rfloor + 1) \times 2^i$
Hence $\lfloor a/2^{i} \rfloor \times 2^{i} \le y_a \lt (\lfloor a/2^{i} \rfloor +1) \times 2^{i} \le \lfloor b/2^{i} \rfloor \times 2^{i} \le y_b \lt (\lfloor b/2^{i} \rfloor +1) \times 2^{i}$
In other words, $y_a \lt y_b.$
Case $2$: The two identical numbers positioned at $A[a]$ and $A[b]$ are in two adjacent lists, and they are being compared in stage $i$.
When $A[a]$ and $A[b]$ are compared. The algorithm will put $A[a]$ before $A[b]$ in the resulting list. Hence $y_a \lt y_b$ after the stage $i$'s merge.
Case $3$: The two identical numbers positioned at $A[a]$ and $A[b]$ are in the same list. This means they have been compared before stage $i$. In this case, $A[a]$ must be processed and put in the resulting list before $A[b]$. Hence $y_a \lt y_b$ after the stage $i$'s merge.