7.)Is our array-based implementation of merge-sort given in Section 12.2.2

stable? Explain why or why not

-12.2.2-

1 def merge(S1, S2, S):

2 Merge two sorted Python lists S1 and S2 into properly sized list S.

3 i = j = 0

4 while i + j < len(S):

5 if j == len(S2) or (i < len(S1) and S1[i] < S2[j]):

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

7 i += 1

8 else:

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

10 j += 1

Code Fragment 12.1: An implementation of the merge operation for Pythons arraybased

list class.

1 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 S1 = S[0:mid] # copy of first half

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

10 # conquer (with recursion)

11 merge sort(S1) # sort copy of first half

12 merge sort(S2) # sort copy of second half

13 # merge results

14 merge(S1, S2, S) # merge sorted halves back into S