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] <= x
5        then i = i+1
6            exchange A[i] and A[j] 
7 exchange A[i+1] and A[r]
8 return i+1


Quicksort(A, p, r)
1 if p < r
2    then q = Partition(A, p, r)
3        run Quicksort(A, p, q-1)
4        run Quicksort(A, q+1, r) Here, A is an array which represents a deck of cards and comparison operations are performed based on the numbers. Your program should also report the stability of the output for the given input (instance). Here, 'stability of the output' means that: cards with the same value appear in the output in the same order as they do in the input (instance). Input The first line contains an integer 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  ≤ 10 9  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

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

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())
cards = [input() for i in range(n)]
stable = sorted(cards, key=lambda x: int(x.split()[1]))
quick_sort(cards, 0, n - 1)

print("Stable" if stable == cards else "Not stable")

for card in cards:
    print(card)

Solution (Python):
n = int(input())
A = []
for i in range(n):
    mark,number = map(str,input().split())
    A.append((mark, int(number), i))

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 A, i + 1

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

A = quickSort(A, 0, n-1)

is_stable = True
for i in range(1, len(A)):
    if(A[i-1][1] == A[i][1]) and (A[i-1][2] > A[i][2]):
        is_stable = False
        break
print('Stable') if is_stable else print('Not stable')
for i in range(len(A)):
    print("{0} {1}".format(A[i][0], A[i][1]))

Solution (Python):
from operator import itemgetter 
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)
A = []
n = int(input())
for i in range(n):
    a,b = map(str,input().split())
    A.append([a,int(b)])

B = [i for i in A]
quicksort(A,0,n-1)

B.sort(key=itemgetter(1))

if A == B:
    print("Stable")
else:
    print("Not stable")
for i in A:
    print(i[0],i[1])

Solution (Python):
def readinput():
    n=int(input())
    cards=[]
    nums=set()
    for _ in range(n):
        m,nn=input().split()
        nn=int(nn)
        cards.append((m,nn))
        nums.add(nn)
    return n,cards, nums

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

def quickSort(cards,p,r):
    if (p<r):
        q=partition(cards,p,r)
        quickSort(cards,p,q-1)
        quickSort(cards,q+1,r)

def getMarks(cards,n):
    marks=[]
    for card in cards:
        if(card[1]==n):
            marks.append(card[0])
    return marks

def isStable(cards0, cards1, nums):
    for n in nums:
        marks0=getMarks(cards0,n)
        marks1=getMarks(cards1,n)
        if(marks0!=marks1):
            return False
    return True

def main(n,cards,nums):
    original = cards.copy()
    quickSort(cards,0,n-1)
    ans=isStable(original, cards, nums)
    if(ans==True):
        print('Stable')
    else:
        print('Not stable')
    for card in cards:
        print(card[0]+' '+str(card[1]))
    return

if __name__=='__main__':
    n,cards,nums=readinput()
    main(n,cards,nums)

Solution (Python):
from collections import deque, defaultdict


def partition(A, p, r):
    x = int(A[r][1:])
    i = p - 1
    for j in range(p, r):
        if x >= int(A[j][1:]):
            i += 1
            A[i], A[j] = A[j], A[i]

    A[i+1], A[r] = A[r], A[i+1]

    return i + 1


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)


def main():
    n = int(input())
    A = []
    d = defaultdict(deque)
    stable = True
    for i in range(n):
        inp = input().replace(" ", "")
        A.append(inp)
        d[int(inp[1:])].append(inp[0])
    quick_sort(A, 0, n-1)

    
    for a in A:
        tmp = d[int(a[1:])].popleft()
        if a[0] != tmp:
            stable = False

    if stable:
        print("Stable")

    else:
        print("Not stable")

    for a in A:
        print(a[0], a[1:])


if __name__ == "__main__":
    main()

Solution (Python):
import copy
def partition(a, p, r):
    x = a[r]
    i = p - 1
    for j in range(p,r):
        if a[j][1] <= x[1]:
            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)  


    
n = int(input())
a = []
for i in range(n):
    a.append(list(input().split()))
    a[i][1]=int(a[i][1])
b = copy.deepcopy(a)

quickSort(a, 0, n-1)

for i in range(n-1):
    if a[i][1] == a[i+1][1]:
        if b.index(a[i]) > b.index(a[i+1]):
            print("Not stable")
            break
else:
    print("Stable")

for i in a:
    print(" ".join(map(str,i)))

Solution (Python):


def partition(A, p, r):
   x = A[r][1]
   i = p-1
   for j in range(p, r):
     if A[j][1] <= x:
       i = 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)
























n = int(input())
A = [[0 for j in range(3)] for i in range(n)]

for i in range(n):
    A[i][0],A[i][1] = input().split()
    A[i][1] = int(A[i][1])
    A[i][2] = i
    

quicksort(A, 0, n-1)







stable_FLG = True
for i in range(1,n):
    if A[i][1] == A[i-1][1] and A[i][2] < A[i-1][2]:
        stable_FLG = False
        break

if stable_FLG:
    print("Stable")
else:
    print("Not stable")


for i in range(n):
    print(A[i][0],A[i][1])

Solution (Python):
import math
import copy

n = int(input())
A = [None for i in range(n)]
for i in range(n):
    a, b = input().split()
    A[i] = [a, int(b)]
inf = 10**9

def merge(A,left,mid,right):
	
	L = A[left:mid] + [[inf,inf]]
	R = A[mid:right] + [[inf,inf]]
	i = 0
	j = 0

	for k in range(left,right):
		
		if L[i][1] <= R[j][1]:
			A[k] = L[i]
			i += 1
		else:
			A[k] = R[j]
			j += 1

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 partition(A,p,r):
	x = A[r][1]
	i = p
	for j in range(p,r):
		if A[j][1] <= x:
			A[i], A[j] = A[j], A[i]
			i = i+1
	A[i], A[r] = A[r], A[i]

	return i

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


B = copy.deepcopy(A)
mergeSort(A,0,n)
quickSort(B,0,n-1)

if A == B:
	print("Stable")
else:
	print("Not stable")

ans = [str(x[0]) +" "+str(x[1]) for x in B]
ans = '\n'.join(ans)
print(ans)

Solution (Python):
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)


n = int(input())
A = [(t[0], int(t[1]), i) for t, i in [(input().split(), i) for i in range(n)]]
quicksort(A, 0, n-1)
notstable = any([True for i in range(1, n) if A[i][1] == A[i-1][1] and A[i][2] < A[i-1][2]])
print("Not stable" if notstable else "Stable")
for v in A:
    print(f"{v[0]} {v[1]}")

Solution (Python):
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 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)

def merge(A, left, right, mid):
    lstl = [[A[i][0], A[i][1]] for i in range(left, mid) ] + [[None, 1000000000]]
    lstr = [[A[i][0], A[i][1]] for i in range(mid, right)] + [[None, 1000000000]]
    pl = 0
    pr = 0
    for _ in range(left, right):
        if lstl[pl][1] <= lstr[pr][1]:
            A[left + pl + pr] = lstl[pl]
            pl += 1
        else:
            A[left + pr + pl] = lstr[pr]
            pr += 1

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


import sys
input = sys.stdin.readline

n = int(input())
A_q = []
A_m = []
for _ in range(n):
    card = input().split()
    A_q.append([card[0], int(card[1])])
    A_m.append([card[0], int(card[1])])

quick_sort(A_q, 0, n-1)
merge_sort(A_m, 0, n)

if A_q == A_m:
    print("Stable")
else:
    print("Not stable")

for i in range(n):
    print(" ".join(map(str, A_q[i])))

Solution (Python):
import sys

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

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

N = int(input())
A = []
D = {}
for i in range(N):
    v, d = sys.stdin.readline().split()
    A.append((v, int(d)))
    D.setdefault(int(d), []).append(v)
    
out_A = quickSort(A,0,N-1)

D = {k: iter(v).__next__ for k, v in D.items()}

ok = 1
for v, d in A:
    if D[d]() != v:
        ok = 0
                
if ok:
    print("Stable")
else:
    print("Not stable")

for i in range(N):
    print(*out_A[i],sep=" ")

Solution (Python):
import copy
def partition(a, p, r):
    x = a[r]
    i = p - 1
    for j in range(p,r): 
        if a[j][1] <= x[1]:
            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)  



n = int(input())
a = []
for i in range(n):
    a.append(list(input().split()))
    a[i][1]=int(a[i][1])
b = copy.deepcopy(a)

quickSort(a, 0, n-1)

for i in range(n-1):
    if a[i][1] == a[i+1][1]:
        if b.index(a[i]) > b.index(a[i+1]):
            print("Not stable")
            break
else:
    print("Stable")

for i in a:
    print(" ".join(map(str,i)))

Solution (Python):
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 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())
card = []
tmpdic = {}
for i in range(n):
    suit, num = input().split()
    num = int(num)
    card.append((suit, num))
    if num in tmpdic:
        tmpdic[num] += suit
    else:
        tmpdic[num] = suit

order = ""
for i in sorted(tmpdic.keys()):
    order += tmpdic[i]

quick_sort(card, 0, n-1)

for i in range(n):
    if order[i] != card[i][0]:
        print("Not stable")
        break
    if i == n-1:
        print("Stable")

for suit, num in card:
    print(f"{suit} {num}")

Solution (Python):
from sys import stdin
N=int(input())
num_list=[]
for i in range(N):
    line = list(stdin.readline().strip().split())
    num_list.append([line[0],int(line[1]),i])
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 check(A):
    for i in range(N-1):
        if A[i][1]==A[i+1][1]:
            if A[i][2]>A[i+1][2]:
                return 0
    return 1
quicksort(num_list,0,N-1)
if check(num_list):
    print("Stable")
else:print("Not stable")
for i in num_list:
    del i[2]
    print(*i)

Solution (Python):
from collections import defaultdict

n=int(input())
cards=[0]*n
A=[0]*n
inds=[0]*n
d=defaultdict(lambda :[])
di=defaultdict(int)
for i in range(n):
    tmp=input().split()
    cards[i]=tmp[0],int(tmp[1])
    A[i]=int(tmp[1])
    inds[i]=i
    d[int(tmp[1])].append(tmp[0])

def partition(A,inds,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]
            inds[i],inds[j]=inds[j],inds[i]
    A[i+1],A[r]=A[r],A[i+1]
    inds[i+1],inds[r]=inds[r],inds[i+1]
    return i+1

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

quicksort(A,inds,0,n-1)

stable_flag=True
for i in range(n):
    num_i=cards[inds[i]][1]
    suit=cards[inds[i]][0]

    if d[num_i][di[num_i]] != suit:
        stable_flag=False
        break
    di[num_i]+=1

if stable_flag:
    print("Stable")
else:
    print("Not stable")

for i in range(n):
    print(*cards[inds[i]])

Solution (Python):
def partition(A, l, r):
    i = l - 1
    for j in range(l, r):
        if int(A[j][1]) <= int(A[r][1]):
            i += 1
            A[i], A[j] = A[j], A[i]
    A[i + 1], A[r] = A[r], A[i + 1]
    return i + 1

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

n = int(input())
arr = [input().split() + [i] for i in range(n)]
quick_sort(arr, 0, n - 1)
tag = True
for i in range(1, n):
    if arr[i][1] == arr[i - 1][1] and arr[i - 1][2] > arr[i][2]:
        tag = False
        break
print(['Not stable', 'Stable'][tag])
for s in arr:
    print(*s[:2])

Solution (Python):
N = int(input())
A1 = []
A2 = []
for _ in range(N):
    a = input().split()
    A1.append((a[0], int(a[1])))
    A2.append((a[0], int(a[1])))

snt = 10 ** 9 + 1

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


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)

def merge(A, left, mid, right):
    L = A[left:mid] + [('SNT', snt)]
    R = A[mid:right] + [('SNT', snt)]
    i, j = 0, 0
    for k in range(left, right):
        if L[i][1] <= R[j][1]:
            A[k] = L[i]
            i += 1
        else:
            A[k] = R[j]
            j += 1

def merge_sort(A, 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)

quick_sort(A1, 0, N - 1)
merge_sort(A2, 0, N)

print('Stable' if A1 == A2 else 'Not stable')
for a1 in A1: print(*a1)

Solution (Python):
import copy


n = int(input())
M = []
for _ in range(n):
    m = input().split()
    M.append([m[0], int(m[1])])

_M = copy.deepcopy(M)


def group(arr):
    r = {}
    for a in arr:
        if r.get(a[1]):
            r[a[1]] += a[0]
        else:
            r[a[1]] = a[0]

    return r


def partition(p, r):
    x = M[r][1]
    i = p - 1
    for k in range(p, r):
        if M[k][1] <= x:
            i += 1
            M[i], M[k] = M[k], M[i]
    M[i + 1], M[r] = M[r], M[i + 1]
    return i + 1


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


quick_sort(0, n - 1)

if group(_M) == group(M):
    print('Stable')
else:
    print('Not stable')

for m in M:
    print(m[0], m[1])

Solution (Python):
import math

def partition(A, p, r):
    x = int(A[r][2:])
    i = p-1
    for j in range(p, r):
        if int(A[j][2:]) <= 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 merge(A, left, mid, right):
    n1 = mid - left
    n2 = right - mid
    L = [None for _ in range(n1+1)]
    R = [None for _ in range(n2+1)]
    for i in range(n1):
        L[i] = A[left + i]
    for i in range(n2):
        R[i] = A[mid + i]

    L[n1] = math.inf
    R[n2] = math.inf

    i = 0
    j = 0

    for k in range(left, right):
        try:
            v1 = int(L[i][2:])
        except:
            v1 = L[i]

        try:
            v2 = int(R[j][2:])
        except:
            v2 = R[j]

        if v1 <= v2:
            A[k] = L[i]
            i += 1
        else:
            A[k] = R[j]
            j += 1


def merge_sort(A, 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)

    return A


if __name__ == "__main__":
    n = int(input())
    cards = []
    for i in range(n):
        cards.append(input())

    reference = merge_sort(cards.copy(), 0, n)
    quicksort(cards, 0, n-1)

    if cards == reference:
        print('Stable')
    else:
        print('Not stable')

    for card in cards:
        print(card)

Solution (Python):
import math
n = int(input())
A = []

def partition(A,p,r):

    x = A[r-1][1]
    i = p-1

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

    return i+1


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


def merge(A, left, mid, right):

  L = A[left:mid]
  L.append((1,math.inf))
  R = A[mid:right]
  R.append((1,math.inf))
  i = 0
  j = 0
  for k in range(left,right):

    if L[i][1] <= R[j][1]:
      A[k] = L[i]
      i = i + 1
    else:
      A[k] = R[j]
      j = j + 1


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)



for i in range(n):
   color,number =input().split()
   A.append((color,int(number)))

A_merge = A.copy()
A_quick = A.copy()

mergeSort(A_merge,0,n)
QuickSort(A_quick,0,n)


if A_quick==A_merge: print("Stable")
else: print("Not stable")

for x in A_quick:
    print("%s %d" %(x[0],x[1]))

Solution (Python):
def partition(a,p,r)->int:
    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 quick_sort(a,l,r):
    if l<r:
        q = partition(a,l,r)
        quick_sort(a,l,q-1)
        quick_sort(a,q+1,r)

def check(a):
    for i in range(len(a)):
        j = i+1
        while j<len(a) and a[i][1]==a[j][1]:
            if a[j][2]<a[i][2]:return 'Not stable'
            j+=1
    return 'Stable'

def main():
    n = int(input())
    a = []
    for i in range(n):
        b,c = input().split()
        a.append([b,int(c),i])
    quick_sort(a,0,n-1)
    print (check(a))
    for b,c,_ in a:print (b,c)

if __name__ == '__main__':
    main()

Solution (Python):

class Card():
  def __init__(self, suit, value):
    self.suit = suit
    self.value = int(value)
  
  def __str__(self):
    return " ".join([self.suit, str(self.value)])
  


MAXINT = 1000000000 + 1
def mergesort(X, l, r):
  if l + 1 < r:
    m = (l + r)//2
    mergesort(X,l,m)
    mergesort(X,m ,r)
    merge(X,l, m, r)

def merge(X, l, m, r):
  nl = m - l
  nr = r - m
  L = [X[i] for i in range(l, l + nl)]
  R = [X[i] for i in range(m, m + nr)]
  L.append(Card('', MAXINT))
  R.append(Card('', MAXINT))
  i = 0
  j = 0
  for k in range(l,r):
    if L[i].value <= R[j].value:
      X[k] = L[i]
      i += 1
    else:
      X[k] = R[j]
      j += 1

def swap(A, i, j):
  tmp = A[i]
  A[i] = A[j]
  A[j] = tmp

def partition(S, p, r):
  x = S[r]
  i = p -1
  for j in range(p,r):
    if S[j].value <= x.value:
      i += 1
      swap(S, i, j)
  swap(S, i+1, r)
  return i+1

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

n = int(input())
A = list()
B = list()
for _ in range(n):
  s, v = input().split()
  A.append(Card(s, v))
  B.append(Card(s, v))

mergesort(A, 0, len(A))
quicksort(B, 0, len(B) - 1)

flag = True
for a,b in zip(A,B):
  if a.suit != b.suit:
    flag = False
    break

if flag:
  print("Stable")
else:
  print("Not stable")

for x in B:
  print(x)

Solution (Python):
import copy

INF = 10 ** 10
def merge(A, left, mid, right):
	count = 0
	L = A[left:mid] + [(INF, INF)]
	R = A[mid:right] + [(INF, INF)]

	i, j = 0, 0
	for k in range(left, right):
		count += 1
		if L[i][1] <= R[j][1]:
			A[k] = L[i]
			i += 1
		else:
			A[k] = R[j]
			j += 1
	return count

def mergeSort(A, left, right):
	if left + 1 < right:
		mid = (left + right) // 2
		countL = mergeSort(A, left, mid)
		countR = mergeSort(A, mid, right)
		return merge(A, left, mid, right) + countL + countR
	return 0

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)

n = int(input())
A = [None for _ in range(n)]
for i in range(n):
	a, b = input().split()
	A[i] = (a, int(b))

B = copy.deepcopy(A)
quickSort(A, 0, n - 1)
mergeSort(B, 0, n)

if A == B:
	print("Stable")
else:
	print("Not stable")

for i in range(n):
	print(" ".join(map(str, A[i])))

Solution (Python):



class Card():

    def __init__(self, suit, num):
        self.suit = suit
        self.num = num
    
    def __repr__(self):
        return str(self.suit) + " " + str(self.num)


def partition(A, p, r):
    x = A[r]
    i = p - 1
    for j in range(p, r):
        if A[j].num <= x.num:
            i += 1
            t = A[i]
            A[i] = A[j]
            A[j] = t
    A[r] = A[i + 1]
    A[i + 1] = x
    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 mergesort(A, left, right):
    if left + 1 < right:
        mid = int((left + right) / 2)
        mergesort(A, left, mid)
        mergesort(A, mid, right)
        merge(A, left, mid, right)


def merge(A, left, mid, right):
    i1, i2 = 0, 0
    L = A[left:mid] + [Card("X", 2000000000)]
    R = A[mid:right] + [Card("X", 2000000000)]
    for j in range(left, right):
        if L[i1].num <= R[i2].num:
            A[j] = L[i1]
            i1 += 1
        else:
            A[j] = R[i2]
            i2 += 1


def compareCards(c1, c2):
    return c1.suit == c2.suit and c1.num == c2.num


def compareStacks(A, B):
    for i in range(len(A)):
        if not compareCards(A[i], B[i]):
            return False
    return True


n = int(input())
A, B = [], []
for i in range(n):
    suit, num = input().split()
    A += [Card(suit, int(num))]
    B += [Card(suit, int(num))]
quicksort(A, 0, n - 1)
mergesort(B, 0, n)
if compareStacks(A, B):
    print("Stable")
else:
    print("Not stable")
for a in A:
    print(a)

Solution (Python):
from collections import defaultdict

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

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

n = int(input())
arr = [input().split() for _ in range(n)]
stable_dict = defaultdict(list)
stable_list = []

for a in arr:
    stable_dict[int(a[1])].append(a[0])

stable_dict = sorted(stable_dict.items(), key = lambda x: x[0])

for key, values in stable_dict:
    for v in values:
        stable_list.append([v, str(key)])

quick_sort(arr, 0, n - 1)

is_stable = 'Stable'
for (a, s) in zip(arr, stable_list):
    if ''.join(a) != ''.join(s):
        is_stable = 'Not stable'
        break
print(is_stable)

for a in arr:
    print(*a)

Solution (Python):
class TRAMP:
    def __init__(self,arg_mark,arg_number,arg_input_index):
        self.mark = arg_mark
        self.number = arg_number
        self.input_index = arg_input_index

N = int(input())
table = []
for input_index in range(N):
    mark,number = map(str,input().split())
    table.append(TRAMP(mark,int(number),input_index))

def Partition(left,right):
    global table
    i = left-1
    pivot = table[right].number
    for start in range(left,right):
        if table[start].number <= pivot:
            i += 1
            table[i],table[start] = table[start],table[i]
    table[i+1],table[right] = table[right],table[i+1]
    return i+1

def quickSort(left,right):
        if left < right:
            q = Partition(left,right)
            quickSort(left,q-1)
            quickSort(q+1,right)

quickSort(0,N-1)
stable_FLG = True

for i in range(1,N):
    if table[i].number == table[i-1].number and table[i].input_index < table[i-1].input_index:
        stable_FLG=False
        break

if stable_FLG:
    print("Stable")
else:
    print("Not stable")

for i in range(N):
    print("%s %d"%(table[i].mark,table[i].number))

Solution (Python):


N = int(input())
A = []
for _ in range(N):
    s, a = input().split()
    A.append((s, int(a)))

B = [a for a in A]


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

    A[r], A[i+1] = A[i+1], A[r]
    return i+1


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


INF = float('inf')


def merge(left, mid, right):
    L = B[left:mid]+[('sentinel', INF)]
    R = B[mid:right]+[('sentinel', INF)]
    l = 0
    r = 0

    for i in range(left, right):
        if L[l][1] <= R[r][1]:
            B[i] = L[l]
            l += 1
        else:
            B[i] = R[r]
            r += 1


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


quick_sort(0, N-1)
merge_sort(0, N)

print('Stable' if A == B else 'Not stable')
for s, v in A:
    print(s, v)

Solution (Python):
class Card:
    def __init__(self, num, suit, input_index):
        self.num = num
        self.suit = suit
        self.input_index = input_index


def partition(A, p, r):
    x = A[r - 1].num
    i = p - 1
    for j in range(p, r - 1):
        if A[j].num <= 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 quick_sort(A, p, r):
    if p < r-1:
        index = partition(A, p, r)
        quick_sort(A, p, index)
        quick_sort(A, index, r)


n = int(input())
li = [None] * n
for i in range(n):
    temp_list = list(map(str, input().split()))
    li[i] = Card(int(temp_list[1]), temp_list[0], i)

quick_sort(li, 0, n)

for i in range(n):
    if i < n - 1 and li[i].num == li[i + 1].num and li[i].input_index > li[i + 1].input_index:
        print('Not stable')
        break
    if i == n - 1:
        print('Stable')

for card in li:
    print(card.suit + ' {}'.format(card.num))

Solution (Python):
import sys
sys.setrecursionlimit(2000000000)

N = int(input())
origin_list = [input().split() for _ in range(N)]
card_list = origin_list[:]
card_list2 = sorted(card_list[:], key=lambda x:x[1])

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)

quickSort(card_list, 0, len(card_list)-1)


if card_list == card_list2:
    print('Stable')
else:
    print('Not stable')

for item in card_list:
    print(*item)

Solution (Python):
import sys,collections
n = int(sys.stdin.readline())

A = [[x,int(y)] for x,y in [line.split() for line in sys.stdin.readlines()]]
d = {}
for i,p in enumerate(A):
  d[str(p)]=i
def partition(A,p,r):
  x = A[r][1] 
  i = p    
  for j in range(p,r): 
    if A[j][1] <= x:
      A[i],A[j] = A[j],A[i]
      i += 1
  A[i],A[r] = A[r],A[i]
  return i
def quicksort(A,p,r):
  if p < r:
    q = partition(A,p,r)
    quicksort(A,p,q-1)
    quicksort(A,q+1,r)
quicksort(A,0,len(A)-1)
for i in range(1,n):
  if A[i-1][1]==A[i][1] and d[str(A[i-1])] > d[str(A[i])]:
    print("Not stable")
    print("\n".join([p[0]+" "+str(p[1]) for p in A]))
    exit(0)
print("Stable")
print("\n".join([p[0]+" "+str(p[1]) for p in A]))

Solution (Python):
class card():
    def __init__(self, suit, number):
        self.s = suit
        self.n = number

def Partition(A, p, r):
    x = int(A[r].n)
    i = p - 1

    for j in range(p, r):
        if int(A[j].n) <= 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 Main():

    n = int(input())
    cards = list()
    
    for i in range(n):
        S, N = input().split()
        c = card(S, N)
        cards.append(c)

    reference = sorted(cards, key=lambda x: int(x.n))
    QuickSort(cards, 0, len(cards) - 1)

    flag = 1

    for i in range(len(cards)):
        if cards[i].s != reference[i].s or cards[i].n != reference[i].n :
            flag = 0
            break;
    
    if flag:
        print("Stable")
    else:
        print("Not stable")

    for i in range(len(cards)):
        print("{0} {1}".format(cards[i].s, cards[i].n))
        
Main()