Is our array$-$based implementation of merge$-$sort given in Section $12\mathrm{.}2\mathrm{.}2$ stable? Explain why or why not. Which specific line$($s$)$ are responsible in making it stable or unstable?

def merge$\_$sort$($S$)$:

$2$Sort the elements of Python list S using the merge$-$sort algorithm.$$

$3$ n $=$ len$($S$)$

$4$ if n $<2$:

$5$ return # list is already sorted

$6$ # divide

$7$ mid $=$ n $//2$

$8$ S$1=$ S$[0$:mid$]$ # copy of first half

$9$ S$2=$ S$[$mid:n$]$ # copy of second half

$10$ # conquer $($with recursion$)$

$11$ merge$\_$sort$($S$1)$ # sort copy of first half

$12$ merge$\_$sort$($S$2)$ # sort copy of second half

$13$ # merge results

$14$ merge$($S$1,$ S$2,$ S$)$ # merge sorted halves back into S

$1$ def merge$($S$1,$ S$2,$ S$)$:

$2$Merge two sorted Python lists S$1$ and S$2$ into properly sized list S$.$

$3$ i$=$j$=0$

$4$ while i$+$j $<$ len$($S$)$:

$5$ if j $==$ len$($S$2)$ or $($i $<$ len$($S$1)$ and S$1[$i$]<$ S$2[$j$])$:

$6$ S$[$i$+$j$]=$ S$1[$i$]$ # copy ith element of S$1$ as next item of S

$7$ i $+=1$

$8$ else:

$9$ S$[$i$+$j$]=$ S$2[$j$]$ # copy jth element of S$2$ as next item of S

$1$ j $+=1$