Problem:


Quick Sort

Let's arrange a deck of cards. Your task is to sort totally n cards. A card consists of a part of a suit (S, H, C or D) and an number. Write a program which sorts such cards based on the following pseudocode:

Partition(A, p, r)
1 x = A[r]
2 i = p-1
3 for j = p to r-1
4     do if A[j] n, the number of cards.

n cards are given in the following lines. Each card is given in a line and represented by a pair of a character and an integer separated by a single space.

Output

In the first line, print the stability ("Stable" or "Not stable") of this output.

In the following lines, print the arranged cards in the same manner of that of the input.

Constraints

1 ≤ n ≤ 100,000

1 ≤ the number of a card  ≤ 109

There are no identical card in the input

Sample Input 1

6
D 3
H 2
D 1
S 3
D 2
C 1

Sample Output 1

Not stable
D 1
C 1
D 2
H 2
D 3
S 3

Sample Input 2

2
S 1
H 1

Sample Output 2

Stable
S 1
H 1



Sample input:
6
D 3
H 2
D 1
S 3
D 2
C 1


Sample output:
Not stable
D 1
C 1
D 2
H 2
D 3
S 3

Submission status: Wrong Answer

Solution code:
import copy

def merge(A, left, mid, right):
    SENTINEL = 10 ** 9
    L = A[left:mid] + [Card('D', SENTINEL)]
    R = A[mid:right] + [Card('D', SENTINEL)]
    # print('L', L)
    # print('R', R)

    i = 0
    j = 0
    for k in range(left, right):
        # print(vars(L[i]))
        # print(vars(R[i]))
        if L[i].number <= R[j].number:
            A[k] = L[i]
            i += 1
        else:
            A[k] = R[j]
            j += 1
    # print('l', left, 'm', mid, 'r', right, A, count)

def merge_sort(A, left, right):
    # print('merge_sort', left, right)
    if left + 1 < right:
        mid = (left + right) // 2
        merge_sort(A, left, mid)
        merge_sort(A, mid, right)
        merge(A, left, mid, right)
def partition(A, p, r):
    x = A[r].number
    i = p - 1
    for j in range(p, r):
        if A[j].number <= x:
            i += 1
            A[i], A[j] = A[j], A[i]
    A[i+1], A[r] = A[r], A[i+1]
    return i + 1

class Card:
    def __init__(self, suit, number):
        self.suit = suit
        self.number = number

def quick_sort(A, p, r):
    if p < r:
        q = partition(A, p, r)
        quick_sort(A, p, q-1)
        quick_sort(A, q+1, r)

n = int(input())
A = []
for i in range(n):
    suit, number = input().split()
    A.append(Card(suit, int(number)))
# print(A)

quick_sort(A, 0, len(A)-1)
# print('quick_sort')
quick_sorted_A = copy.deepcopy(A)

merge_sort(A, 0, len(A))
# print('merge_sort')
# for card in A:
#     print(card.suit, card.number, id(card))


is_stable = True
for i in range(len(A)):
    print(quick_sorted_A[i].suit, A[i].suit)
    if not (quick_sorted_A[i].suit == A[i].suit):
        is_stable = False
        break

if is_stable:
    print('Stable')
else:
    print('Not stable')

for card in quick_sorted_A:
    print(card.suit, card.number)

Submission status: Wrong Answer

Solution code:
from copy import deepcopy

def Partition(A, p, r):
    x = A[r][1]
    i = p-1
    for j in range(p, r):
        if A[j][1] <= x:
            i += 1
            A[i], A[j] = A[j], A[i]
    A[i+1], A[r] = A[r], A[i+1]
    return i+1

def Quicksort(A, p, r):
    if p < r:
        q = Partition(A, p, r)
        Quicksort(A, p, q-1)
        Quicksort(A, q+1, r)

def isStable(cards, comp_cards):
    for card in cards:
        for comp_card in comp_cards:
            if card[1] == comp_card[1]:
                if card[0] != comp_card[0]:
                    return False
                else:
                    comp_card[1] = -1
    return True

n = int(input())
cards = []
for i in range(n):
    card = input().split()
    card[1] = int(card[1])
    cards.append(card)
prev_cards = deepcopy(cards)
sorted(prev_cards, key=lambda card: card[1])

Quicksort(cards, 0, n-1)

if cards == prev_cards:
    print("Stable")
else:
    print("Not stable")
for card in cards:
    print(' '.join(map(str, card)))

Submission status: Wrong Answer

Solution code:
def partition(a,p,r):
    x=a[r][1:]
    i=p-1
    for j in range(p,r):
        if(a[j][1:]<=x):
            i+=1
            a[i],a[j]=a[j],a[i]
    a[i+1],a[r]=a[r],a[i+1]
    return i+1

def quicksort(a,p,r):
    if(p<r):
        q=partition(a,p,r)
        quicksort(a,p,q-1)
        quicksort(a,q+1,r)
        
def strr_bubble_sort(a,n):
    m=0
    flag=True
    while(flag):
        flag=False
        for i in range(n-1,0,-1):
            if(a[i-1][1:] > a[i][1:]):
                tmp=a[i-1]
                a[i-1]=a[i]
                m+=1
                a[i]=tmp
                flag=True
                
    return a

a=[]
n=int(input())
for i in range(n):
    s=input()
    a.append("".join(s.split()))

b=list(a)
strr_bubble_sort(b,n)
c=list(a)
quicksort(c,0,n-1)
dic={"D":[],"H":[],"S":[],"C":[]}

for i in a:
    dic[i[:1]].append(i[1:])

if(b==c):
    print("Stable")
else:
    print("Not stable")
for i in c:
    print("%s %s"%(i[:1],i[1:]))

Submission status: Wrong Answer

Solution code:
def Partition(A,p,r):
    x = A[r]
    i = p-1
    for j in range(p,r):
        if (A[j] <= x):
            i += 1
            A[i],A[j] = A[j],A[i]
    A[i+1],A[r] = A[r],A[i+1]
    return i+1

def qsort(A,p,r):
    if p < r:
        q = Partition(A,p,r)
        qsort(A,p,q-1)
        qsort(A,q+1,r)

class card(object):
    def __init__(self, str):
        data = str.split()
        self.symbol,self.num = data[0],int(data[1])
    
    def __le__(self,obj):
        if(self.num < obj.num):
            return True
        else:
            return False
    def __ge__(self,obj):
        if(self.num > obj.num):
            return True
        else:
            return False

    def display_card(self):
        print("{0} {1}".format(self.symbol,self.num))

c = []        
n = int(input())
while(n>0):
    c.append(card(input()))
    n -= 1
c_org = c.copy()

qsort(c,0,len(c)-1)

notstable = False
for i in range(1,len(c)):
    if(c[i-1].num == c[i].num):
        firstCard = c[i-1]
        secondCard = c[i]
        is_found_1st = False
        is_found_2nd = False

        for org in c_org:
            if(org == firstCard):
                if is_found_2nd:
                    notstable = True
            if(org == secondCard):
                is_found_2nd = True
if(notstable == 1):
    print('Not stable')
else:
    print('Stable')
for x in c:
    x.display_card()

Submission status: Wrong Answer

Solution code:
def partition(data, left, right):
    pivot = int(data[right][2:])
    i = left - 1
    for j in range(left, right):
        if int(data[j][2:]) <= pivot:
            i += 1
            data[i], data[j] = data[j], data[i]
    data[i+1], data[right] = data[right], data[i+1]
    return i+1

def quick_sort(data, left, right):
    if left < right:
        new_pivot = partition(data, left, right)
        quick_sort(data, left, new_pivot-1)
        quick_sort(data, new_pivot+1, right)

#for comparison
def merge(data, left, mid, right):
    n1 = mid - left
    n2 = right - mid
    L = data[left : mid]
    R = data[mid : right]
    L.append("  10000000000")
    R.append("  10000000000")
    i = 0
    j = 0
    for k in range(left, right):
        if int(L[i][2:]) <= int(R[j][2:]):
            data[k] = L[i]
            i += 1
        else:
            data[k] = R[j]
            j += 1

def merge_sort(data, left, right):
    if left + 1 < right:
        mid = (left + right) / 2
        merge_sort(data, left, mid)
        merge_sort(data, mid, right)
        merge(data, left, mid, right)

def main():
    num = raw_input()
    pairs_quick = []
    pairs_check = []
    for i in range(int(num)):
        pair = raw_input()
        pairs_quick.append(pair)
        pairs_check.append(pair)
    
    quick_sort(pairs_quick, 0, int(num)-1)
    merge_sort(pairs_check, 0, int(num)-1)
    if pairs_quick == pairs_check:
        print "Stable"
    else:
        print "Not stable"

    print "\n".join(pairs_quick)

if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
def partition(data, left, right):
    pivot = int(data[right][2:])
    i = left - 1
    for j in range(left, right):
        if int(data[j][2:]) <= pivot:
            i += 1
            data[i], data[j] = data[j], data[i]
    data[i+1], data[right] = data[right], data[i+1]
    return i+1

def quick_sort(data, left, right):
    if left < right:
        new_pivot = partition(data, left, right)
        quick_sort(data, left, new_pivot-1)
        quick_sort(data, new_pivot+1, right)

#for comparison
def merge(data, left, mid, right):
    n1 = mid - left
    n2 = right - mid
    L = data[left : mid]
    R = data[mid : right]
    L.append("  100000000000")
    R.append("  100000000000")
    i = 0
    j = 0
    for k in range(left, right):
        if int(L[i][2:]) <= int(R[j][2:]):
            data[k] = L[i]
            i += 1
        else:
            data[k] = R[j]
            j += 1

def merge_sort(data, left, right):
    if left + 1 < right:
        mid = (left + right) / 2
        merge_sort(data, left, mid)
        merge_sort(data, mid, right)
        merge(data, left, mid, right)

def main():
    num = raw_input()
    pairs_quick = []
    pairs_check = []
    for i in range(int(num)):
        pair = raw_input()
        pairs_quick.append(pair)
        pairs_check.append(pair)
    
    quick_sort(pairs_quick, 0, int(num)-1)
    merge_sort(pairs_check, 0, int(num)-1)
    if pairs_quick == pairs_check:
        print "Stable"
    else:
        print "Not stable"

    print "\n".join(pairs_quick)

if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
def partition(data, left, right):
    pivot = int(data[right][2:])
    i = left - 1
    for j in range(left, right):
        if int(data[j][2:]) <= pivot:
            i += 1
            data[i], data[j] = data[j], data[i]
    data[i+1], data[right] = data[right], data[i+1]
    return i+1

def quick_sort(data, left, right):
    if left < right:
        new_pivot = partition(data, left, right)
        quick_sort(data, left, new_pivot-1)
        quick_sort(data, new_pivot+1, right)

#for comparison
def merge(data, left, mid, right):
    n1 = mid - left
    n2 = right - mid
    L = data[left : mid]
    R = data[mid : right]
    L.append("  10000000000")
    R.append("  10000000000")
    i = 0
    j = 0
    for k in range(left, right):
        if int(L[i][2:]) <= int(R[j][2:]):
            data[k] = L[i]
            i += 1
        else:
            data[k] = R[j]
            j += 1

def merge_sort(data, left, right):
    if left + 1 < right:
        mid = (left + right) / 2
        merge_sort(data, left, mid)
        merge_sort(data, mid, right)
        merge(data, left, mid, right)

def main():
    num = raw_input()
    pairs_quick = []
    pairs_check = []
    for i in range(int(num)):
        pair = raw_input()
        pairs_quick.append(pair)
        pairs_check.append(pair)
    
    quick_sort(pairs_quick, 0, int(num)-1)
    merge_sort(pairs_check, 0, int(num))
    if pairs_quick == pairs_check:
        print "Stable"
    else:
        print "Not stable"

    print "\n".join(pairs_quick)
    print "\n".join(pairs_check)

if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
def partition(a,p,r):
    x=a[r][1:]
    i=p-1
    for j in range(p,r):
        if(a[j][1:]<=x):
            i+=1
            a[i],a[j]=a[j],a[i]
    a[i+1],a[r]=a[r],a[i+1]
    return i+1

def quicksort(a,p,r):
    if(p<r):
        q=partition(a,p,r)
        quicksort(a,p,q-1)
        quicksort(a,q+1,r)
        
def strr_bubble_sort(a,n):
    m=0
    flag=True
    while(flag):
        flag=False
        for i in range(n-1,0,-1):
            if(a[i-1][1:] > a[i][1:]):
                tmp=a[i-1]
                a[i-1]=a[i]
                m+=1
                a[i]=tmp
                flag=True
    return a

a=[]
n=int(input())
for i in range(n):
    s=input()
    a.append("".join(s.split()))

b=list(a)
strr_bubble_sort(b,n)
c=list(a)
quicksort(c,0,n-1)

d=dict()
i=0
x="-1"
for i in c:
    if(x!=i[1:]):
        d[i[1:]]=[i[:1]]
        x=i[1:]
    else:
        d[x].append(i[:1])

message="Stable"

for i in reversed(a):
    if(i[1:] in d):
        if(d[i[1:]].pop()!=i[:1]):
            message="Not stable"
            break

print(message)

for i in c:
    print("%s %s"%(i[:1],i[1:]))

Submission status: Wrong Answer

Solution code:
def partition(a,p,r):
    x=int(a[r][1:])
    i=p-1
    for j in range(p,r):
        if(int(a[j][1:])<=x):
            i+=1
            a[i],a[j]=a[j],a[i]
    a[i+1],a[r]=a[r],a[i+1]
    return i+1

def quicksort(a,p,r):
    if(p<r):
        q=partition(a,p,r)
        quicksort(a,p,q-1)
        quicksort(a,q+1,r)

a=[]
n=int(input())
for i in range(n):
    s=input()
    a.append("".join(s.split()))

c=list(a)
quicksort(c,0,n-1)

d=dict()
i=0
x="-1"
for i in c:
    if(x!=i[1:]):
        d[i[1:]]=[i[:1]]
        x=i[1:]
    else:
        d[x].append(i[:1])
    print(d)

message="Stable"

for i in reversed(a):
    if(i[1:] in d):
        print(d)
        if(d[i[1:]].pop()!=i[:1]):
            message="Not stable"
            break

print(message)

for i in c:
    print("%s %s"%(i[:1],i[1:]))

Submission status: Wrong Answer

Solution code:
n = int(raw_input())
A = list()
for i in range(n):
    A_str = raw_input().split(" ")
    A.append([A_str[0], int(A_str[1])])
A_copy = list(A)

def partition(A):
    i = 0
    r = A[-1][1]
    for j in range(0, len(A)):
        if A[j][1] <= r:
            A[i], A[j] = A[j], A[i]
            i += 1
    return i - 1, A

def quicksort(A):
    if len(A) < 2:
        return A
    q, A = partition(A)
    left = A[:q]
    right = A[q+1:]

    A[:q] = quicksort(left)
    A[q+1:] = quicksort(right)
    return A



def merge(left, right):
    sorted_list = list()
    left_index = 0
    right_index = 0

    while left_index < len(left) and right_index < len(right):
        if left[left_index] <= right[right_index]:
            sorted_list.append(left[left_index])
            left_index += 1

        else:
            sorted_list.append(right[right_index])
            right_index += 1
       
    if left:
        sorted_list.extend(left[left_index:])
    if right:
        sorted_list.extend(right[right_index:])
        
    return sorted_list
    
def mergeSort(A):
    if len(A) <= 1:
        return A

    mid = len(A) // 2
    left = A[:mid]
    right = A[mid:]

    left = mergeSort(left)
    right = mergeSort(right)

    return list(merge(left, right))

A = quicksort(A)
A_copy = mergeSort(A_copy)

flag = 0
for i in range(n):
    if A[i][0] != A_copy[i][0] and A[i][1] == A_copy[i][1]:
        flag = 1
        break

if flag == 0:
    print "Stable"
else:
    print "Not stable"

print A

Submission status: Wrong Answer

Solution code:
def mergesort(A, left, right):
 
    if left + 1 < right:
        mid = (left + right)/2
         
        mergesort(A, left, mid)
        mergesort(A, mid, right)
        merge(A, left, mid, right)
 
 
def merge(A, left, mid, right):
    
    n1 = mid -left
    n2 = right - mid
    L = []
    R = []
    x = [" "," ", 100000000000000000000]
    for i in range(0, n1):
        L.append(A[left + i])
    for i in range(0, n2):
        R.append(A[mid + i])
    L.append(x)
    R.append(x)
    i = 0
    j = 0
    for k in range(left, right):
        if int(L[i][-1]) <= int(R[j][-1]):
            A[k] = L[i]
            i = i + 1
        else:
            A[k] = R[j]
            j = j + 1
            
            
            
def partition(A, p, r):
    x = int(A[r-1][2])
    i = p - 1
    for j in range(p, r-1):
        if int(A[j][2]) <= x:
            i = i + 1
            A[i],A[j]=A[j], A[i]
             
    A[i+1], A[r-1]=A[r-1], A[i+1]
     
    return i+1
 
def quicksort(A, p, r):
    if p < r-1:
        q = partition(A, p, r)
         
        quicksort(A, p, q)
        quicksort(A, q+1, r)
 
 
 
 
if __name__ == "__main__":
    num = int(raw_input())
    num_list = []
    num_list1 = []
    for i in range(num):
        num_list.append(raw_input())
    num_list1 = list(num_list)
    quicksort(num_list, 0, len(num_list))
  
    mergesort(num_list1, 0, len(num_list1))
     
    if num_list == num_list1:
        print ("Stable")
    else:
        print ("Not stable")
    print "\n".join(num_list)

Submission status: Wrong Answer

Solution code:
def mergesort(A, left, right):
 
    if left + 1 < right:
        mid = (left + right)/2
         
        mergesort(A, left, mid)
        mergesort(A, mid, right)
        merge(A, left, mid, right)
 
 
def merge(A, left, mid, right):
    
    n1 = mid -left
    n2 = right - mid
    L = []
    R = []
    x = [" "," ", 10000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000]
    for i in range(0, n1):
        L.append(A[left + i])
    for i in range(0, n2):
        R.append(A[mid + i])
    L.append(x)
    R.append(x)
    i = 0
    j = 0
    for k in range(left, right):
        if int(L[i][-1]) <= int(R[j][-1]):
            A[k] = L[i]
            i = i + 1
        else:
            A[k] = R[j]
            j = j + 1
            
            
            
def partition(A, p, r):
    x = int(A[r-1][2])
    i = p - 1
    for j in range(p, r-1):
        if int(A[j][2]) <= x:
            i = i + 1
            A[i],A[j]=A[j], A[i]
             
    A[i+1], A[r-1]=A[r-1], A[i+1]
     
    return i+1
 
def quicksort(A, p, r):
    if p < r-1:
        q = partition(A, p, r)
         
        quicksort(A, p, q)
        quicksort(A, q+1, r)
 
 
 
 
if __name__ == "__main__":
    num = int(raw_input())
    num_list = []
    num_list1 = []
    for i in range(num):
        num_list.append(raw_input())
    num_list1 = list(num_list)
    quicksort(num_list, 0, len(num_list))
  
    mergesort(num_list1, 0, len(num_list1))
     
    if num_list == num_list1:
        print ("Stable")
    else:
        print ("Not stable")
    print "\n".join(num_list)

Submission status: Wrong Answer

Solution code:
def mergesort(A, left, right):
 
    if left + 1 < right:
        mid = (left + right)/2
         
        mergesort(A, left, mid)
        mergesort(A, mid, right)
        merge(A, left, mid, right)
 
 
def merge(A, left, mid, right):
    
    n1 = mid -left
    n2 = right - mid
    L = []
    R = []
    x = [" "," ", 1000000000000000000000000000000000000000000]
    for i in range(0, n1):
        L.append(A[left + i])
    for i in range(0, n2):
        R.append(A[mid + i])
    L.append(x)
    R.append(x)
    i = 0
    j = 0
    for k in range(left, right):
        if int(L[i][-1]) <= int(R[j][-1]):
            A[k] = L[i]
            i = i + 1
        else:
            A[k] = R[j]
            j = j + 1
            
            
            
def partition(A, p, r):
    x = int(A[r-1][2])
    i = p - 1
    for j in range(p, r-1):
        if int(A[j][2]) <= x:
            i = i + 1
            A[i],A[j]=A[j], A[i]
             
    A[i+1], A[r-1]=A[r-1], A[i+1]
     
    return i+1
 
def quicksort(A, p, r):
    if p < r-1:
        q = partition(A, p, r)
         
        quicksort(A, p, q)
        quicksort(A, q+1, r)
 
 
 
 
if __name__ == "__main__":
    num = int(raw_input())
    num_list = []
    num_list1 = []
    for i in range(num):
        num_list.append(raw_input())
    num_list1 = list(num_list)
    quicksort(num_list, 0, len(num_list))
  
    mergesort(num_list1, 0, len(num_list1))
     
    if num_list == num_list1:
        print ("Stable")
    else:
        print ("Not stable")
    print "\n".join(num_list)

Submission status: Wrong Answer

Solution code:
def mergesort(A, left, right):
 
    if left + 1 < right:
        mid = (left + right)/2
         
        mergesort(A, left, mid)
        mergesort(A, mid, right)
        merge(A, left, mid, right)
 
 
def merge(A, left, mid, right):
    
    n1 = mid -left
    n2 = right - mid
    L = []
    R = []
    x = [" "," ", 1000000000000000000000000000000]
    for i in range(0, n1):
        L.append(A[left + i])
    for i in range(0, n2):
        R.append(A[mid + i])
    L.append(x)
    R.append(x)
    i = 0
    j = 0
    for k in range(left, right):
        if int(L[i][-1]) <= int(R[j][-1]):
            A[k] = L[i]
            i = i + 1
        else:
            A[k] = R[j]
            j = j + 1
            
            
            
def partition(A, p, r):
    x = int(A[r-1][2])
    i = p - 1
    for j in range(p, r-1):
        if int(A[j][2]) <= x:
            i = i + 1
            A[i],A[j]=A[j], A[i]
             
    A[i+1], A[r-1]=A[r-1], A[i+1]
     
    return i+1
 
def quicksort(A, p, r):
    if p < r-1:
        q = partition(A, p, r)
         
        quicksort(A, p, q)
        quicksort(A, q+1, r)
 
 
 
 
if __name__ == "__main__":
    num = int(raw_input())
    num_list = []
    num_list1 = []
    for i in range(num):
        num_list.append(raw_input())
    num_list1 = list(num_list)
    quicksort(num_list, 0, len(num_list))
  
    mergesort(num_list1, 0, len(num_list1))
     
    if num_list == num_list1:
        print ("Stable")
    else:
        print ("Not stable")
    print "\n".join(num_list)

Submission status: Wrong Answer

Solution code:
def mergesort(A, left, right):
 
    if left + 1 < right:
        mid = (left + right)/2
         
        mergesort(A, left, mid)
        mergesort(A, mid, right)
        merge(A, left, mid, right)
 
 
def merge(A, left, mid, right):
    
    n1 = mid -left
    n2 = right - mid
    L = []
    R = []
    x = [" "," ", 1000000000000000000000000000000]
    for i in range(0, n1):
        L.append(A[left + i])
    for i in range(0, n2):
        R.append(A[mid + i])
    L.append(x)
    R.append(x)
    i = 0
    j = 0
    for k in range(left, right):
        if int(L[i][-1]) <= int(R[j][-1]):
            A[k] = L[i]
            i = i + 1
        else:
            A[k] = R[j]
            j = j + 1
            
            
            
def partition(A, p, r):
    x = int(A[r-1][2])
    i = p - 1
    for j in range(p, r-1):
        if int(A[j][2]) <= x:
            i = i + 1
            A[i],A[j]=A[j], A[i]
             
    A[i+1], A[r-1]=A[r-1], A[i+1]
     
    return i+1
 
def quicksort(A, p, r):
    if p < r-1:
        q = partition(A, p, r)
         
        quicksort(A, p, q)
        quicksort(A, q+1, r)
 
 
 
 
if __name__ == "__main__":
    num = int(raw_input())
    num_list = []
    num_list1 = []
    for i in range(num):
        num_list.append(raw_input())
    num_list1 = list(num_list)
    quicksort(num_list, 0, len(num_list))
  
    mergesort(num_list1, 0, len(num_list1))
     
    if num_list == num_list1:
        print ("Sttable")
    else:
        print ("Not stable")
    print "\n".join(num_list)

Submission status: Wrong Answer

Solution code:
def mergesort(A, left, right):
 
    if left + 1 < right:
        mid = (left + right)/2
         
        mergesort(A, left, mid)
        mergesort(A, mid, right)
        merge(A, left, mid, right)
 
 
def merge(A, left, mid, right):
    
    n1 = mid -left
    n2 = right - mid
    L = []
    R = []
    x = [" "," ", 10000000000]
    for i in range(0, n1):
        L.append(A[left + i])
    for i in range(0, n2):
        R.append(A[mid + i])
    L.append(x)
    R.append(x)
    i = 0
    j = 0
    for k in range(left, right):
        if int(L[i][-1]) <= int(R[j][-1]):
            A[k] = L[i]
            i = i + 1
        else:
            A[k] = R[j]
            j = j + 1
            
            
            
def partition(A, p, r):
    x = int(A[r-1][2])
    i = p - 1
    for j in range(p, r-1):
        if int(A[j][2]) <= x:
            i = i + 1
            A[i],A[j]=A[j], A[i]
             
    A[i+1], A[r-1]=A[r-1], A[i+1]
     
    return i+1
 
def quicksort(A, p, r):
    if p < r-1:
        q = partition(A, p, r)
         
        quicksort(A, p, q)
        quicksort(A, q+1, r)
 
 
 
 
if __name__ == "__main__":
    num = int(raw_input())
    num_list = []
    num_list1 = []
    for i in range(num):
        num_list.append(raw_input())
    num_list1 = list(num_list)
    quicksort(num_list, 0, len(num_list))
  
    mergesort(num_list1, 0, len(num_list1))
     
    if num_list == num_list1:
        print ("Stable")
    else:
        print ("Not stable")
    print "\n".join(num_list)

Submission status: Wrong Answer

Solution code:
def mergesort(A, left, right):
 
    if left + 1 < right:
        mid = (left + right)/2
         
        mergesort(A, left, mid)
        mergesort(A, mid, right)
        merge(A, left, mid, right)
 
 
def merge(A, left, mid, right):
    
    n1 = mid -left
    n2 = right - mid
    L = []
    R = []
    x = [" "," ", 100000]
    for i in range(0, n1):
        L.append(A[left + i])
    for i in range(0, n2):
        R.append(A[mid + i])
    L.append(x)
    R.append(x)
    i = 0
    j = 0
    for k in range(left, right):
        if int(L[i][-1]) <= int(R[j][-1]):
            A[k] = L[i]
            i = i + 1
        else:
            A[k] = R[j]
            j = j + 1

            
            
            
def partition(A, p, r):
    x = int(A[r-1][2])
    i = p - 1
    for j in range(p, r-1):
        if int(A[j][2]) <= x:
            i = i + 1
            A[i],A[j]=A[j], A[i]
             
    A[i+1], A[r-1]=A[r-1], A[i+1]
    return i+1
 
def quicksort(A, p, r):
    if p < r-1:
        q = partition(A, p, r)
         
        quicksort(A, p, q)
        quicksort(A, q+1, r)
 
 
 
 
if __name__ == "__main__":
    num = int(raw_input())
    num_list = []
    num_list1 = []
    for i in range(num):
        num_list.append(raw_input())
    num_list1 = list(num_list)
    quicksort(num_list, 0, len(num_list))
  
    mergesort(num_list1, 0, len(num_list1))
     
    if num_list == num_list1:
        print ("Stable")
    else:
        print ("Not stable")

    print "\n".join(num_list1)

Submission status: Wrong Answer

Solution code:
def mergesort(A, left, right):
 
    if left + 1 < right:
        mid = (left + right)/2
         
        mergesort(A, left, mid)
        mergesort(A, mid, right)
        merge(A, left, mid, right)
 
 
def merge(A, left, mid, right):
    
    n1 = mid -left
    n2 = right - mid
    L = []
    R = []
    x = [" "," ", 100000]
    for i in range(0, n1):
        L.append(A[left + i])
    for i in range(0, n2):
        R.append(A[mid + i])
    L.append(x)
    R.append(x)
    i = 0
    j = 0
    for k in range(left, right):
        if int(L[i][-1]) <= int(R[j][-1]):
            A[k] = L[i]
            i = i + 1
        else:
            A[k] = R[j]
            j = j + 1
            
            
def partition(A, p, r):
    x = int(A[r-1][2])
    i = p - 1
    for j in range(p, r-1):
        if int(A[j][2]) <= x:
            i = i + 1
            A[i],A[j]=A[j], A[i]
             
    A[i+1], A[r-1]=A[r-1], A[i+1]
    return i+1
 
def quicksort(A, p, r):
    if p < r-1:
        q = partition(A, p, r)
         
        quicksort(A, p, q)
        quicksort(A, q+1, r)
 
 
 
 
if __name__ == "__main__":
    num = int(raw_input())
    num_list = []
    num_list1 = []
    for i in range(num):
        num_list.append(raw_input())
    num_list1 = list(num_list)
    quicksort(num_list, 0, len(num_list))
  
    mergesort(num_list1, 0, len(num_list1))
     
    if num_list == num_list1:
        print ("Stable")
    else:
        print ("Not stable")
    print "\n".join(num_list1)

Submission status: Wrong Answer

Solution code:
def mergesort(A, left, right):
 
    if left + 1 < right:
        mid = (left + right)/2
         
        mergesort(A, left, mid)
        mergesort(A, mid, right)
        merge(A, left, mid, right)
 
 
def merge(A, left, mid, right):
    
    n1 = mid -left
    n2 = right - mid
    L = []
    R = []
    x = [" "," ", 100000]
    for i in range(0, n1):
        L.append(A[left + i])
    for i in range(0, n2):
        R.append(A[mid + i])
    L.append(x)
    R.append(x)
    i = 0
    j = 0
    for k in range(left, right):
        if int(L[i][-1]) <= int(R[j][-1]):
            A[k] = L[i]
            i = i + 1
        else:
            A[k] = R[j]
            j = j + 1
            
            
def partition(A, p, r):
    x = int(A[r-1][2])
    i = p - 1
    for j in range(p, r-1):
        if int(A[j][2]) <= x:
            i = i + 1
            A[i],A[j]=A[j], A[i]
             
    A[i+1], A[r-1]=A[r-1], A[i+1]
    return i+1
 
def quicksort(A, p, r):
    if p < r-1:
        q = partition(A, p, r)
         
        quicksort(A, p, q)
        quicksort(A, q+1, r)
 
 
 
 
if __name__ == "__main__":
    num = int(raw_input())
    num_list = []
    num_list1 = []
    for i in range(num):
        num_list.append(raw_input())
    num_list1 = list(num_list)
    quicksort(num_list, 0, len(num_list))
  
    mergesort(num_list1, 0, len(num_list1))
     
    if num_list == num_list1:
        print ("Stable")
    else:
        print ("Not stable")
    print "\n".join(num_list)

Submission status: Wrong Answer

Solution code:
def mergesort(A, left, right):
 
    if left + 1 < right:
        mid = (left + right)/2
         
        mergesort(A, left, mid)
        mergesort(A, mid, right)
        merge(A, left, mid, right)
 
 
def merge(A, left, mid, right):
    
    n1 = mid -left
    n2 = right - mid
    L = []
    R = []
    x = [" "," ", 999999999999999999]
    for i in range(0, n1):
        L.append(A[left + i])
    for i in range(0, n2):
        R.append(A[mid + i])
    L.append(x)
    R.append(x)
    i = 0
    j = 0
    for k in range(left, right):
        if int(L[i][-1]) <= int(R[j][-1]):
            A[k] = L[i]
            i = i + 1
        else:
            A[k] = R[j]
            j = j + 1
            
            
def partition(A, p, r):
    x = int(A[r-1][2])
    i = p - 1
    for j in range(p, r-1):
        if int(A[j][2]) <= x:
            i = i + 1
            A[i],A[j]=A[j], A[i]
             
    A[i+1], A[r-1]=A[r-1], A[i+1]
    return i+1
 
def quicksort(A, p, r):
    if p < r-1:
        q = partition(A, p, r)
         
        quicksort(A, p, q)
        quicksort(A, q+1, r)
 
 
 
 
if __name__ == "__main__":
    num = int(raw_input())
    num_list = []
    num_list1 = []
    for i in range(num):
        num_list.append(raw_input())
    num_list1 = list(num_list)
    quicksort(num_list, 0, len(num_list))
  
    mergesort(num_list1, 0, len(num_list1))
     
    if num_list == num_list1:
        print ("Stable")
    else:
        print ("Not stable")
    print "\n".join(num_list)