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):
import copy
INF = 10000000000
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]
            flag = 1
    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)

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 = count + 1
        if L[i][1] <= R[j][1]:
            A[k] = L[i]
            i = i + 1
        else:
            A[k] = R[j]
            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

N = int(input())
C = []
for i in range(N):
    C.append(input().split())
    C[i][1] = int(C[i][1])

D = copy.deepcopy(C)
Qsort(C,0,N-1)
mergeSort(D,0,N)

if C==D:
    print("Stable")
else:
    print("Not stable")
for i in range(N):
    print(C[i][0]+" "+str(C[i][1]))

Solution (Python):

import sys

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


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]
    r = A[mid: right]

    l.append([None, float('inf')])
    r.append([None, float('inf')])

    i = 0
    j = 0

    for k in range(left, right, 1):
        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)


n = int(input())
A = []
for i in range(n):
    suit, num = input().split()
    A.append([suit, int(num)])
A1 = A.copy()

quick_sort(A, 0, n-1)
merge_sort(A1, 0, n)

if A != A1:
    print('Not stable')
else:
    print('Stable')

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

Solution (Python):
import sys
input = sys.stdin.readline

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 marge(A, left, right, mid):
    n1 = mid - left
    n2 = right - mid
    L = [[] for _ in range(n1+1)]
    R = [[] 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] = ('Z', 10 ** 9 + 1)
    R[n2] = ('Z', 10 ** 9 + 1)
    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
    return

def margesort(A, left, right):
    if left + 1 < right:
        mid = (left + right) // 2
        margesort(A, left, mid)
        margesort(A, mid, right)
        marge(A, left, right, mid)
        return
    return


def main():
    n = int(input())
    A = [[] for _ in range(n)]
    B = [[] for _ in range(n)]
    for i in range(n):
        a, b = input().split()
        b = int(b)
        A[i] = (a, b)
        B[i] = (a, b)
    margesort(A, 0, n)
    quicksort(B, 0, n-1)
    if A == B:
        print("Stable")
    else:
        print("Not stable")
    for a in B:
        print(a[0], a[1])

if __name__ == '__main__': main()

Solution (Python):
import copy

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)
        

def merge(A, left, mid, right):
    L = A[left:mid] + [("J", 1000000000) ]
    R = A[mid:right] + [("J", 1000000000)]
    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 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)
    
    
n = int(input())
A_Q = [input() for _ in range(n)]
A_Q = [(i.split()[0], int(i.split()[1])) for i in A_Q]
A_M = copy.deepcopy(A_Q)

quicksort(A_Q, 0, n-1)
mergesort(A_M, 0, n)

A_Q = [f"{str(i[0])} {str(i[1])}"for i in A_Q]
A_M = [f"{str(i[0])} {str(i[1])}"for i in A_M]
if A_Q == A_M:
    print("Stable")
else:
    print("Not stable")
print(*A_Q, sep="\n")

Solution (Python):
import sys
import copy

infty = 10**10

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

	n1 = mid -left
	n2 = right - mid

	L = []
	R = []

	for i in range(n1):
		L.append(A[left+i])
	for i in range(n2):
		R.append(A[mid+i])

	eInfty = ['X',infty]
	L.append(eInfty)
	R.append(eInfty)

	i = 0
	j = 0
	cnt = 0

	for k in range(left,right):

		cnt += 1

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

	return cnt


def mergeSort(A,left,right):

	cnt = 0

	if left+1 < right:

		mid = (left + right) // 2
		cnt += mergeSort(A,left,mid)
		cnt += mergeSort(A,mid,right)
		cnt += merge(A,left,mid,right)

	return cnt


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(M,Q):

	for i in range(len(M)):

		if M[i] != Q[i]:

			return False

	return True

def test():

	n = int(sys.stdin.readline())
	deck = []

	for i in range(n):

		inputs = list(sys.stdin.readline().split())
		inputs[1] = int(inputs[1])

		deck.append(inputs)

	original = copy.deepcopy(deck)
	result = mergeSort(original,0,n)

	Quicksort(deck,0,n-1)

	if isStable(original,deck) == True:
		print("Stable")
	else:
		print("Not stable")

	for i in range(n):
		print(f"{deck[i][0]} {deck[i][1]}")


if __name__ == "__main__":
	test()

Solution (Python):
import copy

n = int(input())
A = []

for i in range(n):
    x, y = input().split()
    z = {'mark': x, 'num': int(y)}
    A.append(z)

B = copy.deepcopy(A)

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

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

quicksort(0, n-1)

def checkstable():
    for i in range(n-1):
        if A[i]['num'] == A[i+1]['num']:
            if B.index(A[i]) > B.index(A[i+1]):
                return 'Not stable'
                break
    return 'Stable'

print(checkstable())
for i in A:
    print(i['mark'], i['num'])

Solution (Python):

import copy
 
INF = 10000000000
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 = count + 1
        if L[i][1] <= R[j][1]:
            A[k] = L[i]
            i = i + 1
        else:
            A[k] = R[j]
            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
    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

n = int(input())
A = [input().split() for _ in range(n)]
A = [(a[0], int(a[1])) for a in A]
B = [(a[0], int(a[1])) for a in A]

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, n-1)
mergeSort(B, 0, n)
if A == B:
    print('Stable')
else:
    print("Not stable")
    
ans = [str(a[0])+" "+str(a[1]) for a in A]
ans = '\n'.join(ans)
print(ans)

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

num = int(input())
card_list = [input().split() for s in range(num)]
card_list = [(t[0], int(t[1])) for t in card_list]
cp_card_list = card_list[:]

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

is_stable = True
for i in range(len(card_list) - 1):
    if card_list[i][1] == card_list[i+1][1]:
        if cp_card_list.index(card_list[i]) > cp_card_list.index(card_list[i+1]):
            is_stable = False
            break

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

for t in card_list:
    print(t[0], t[1])

Solution (Python):
class Card:
    def __init__(self):
        self.suit = ''
        self.value = 0

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

def main():
    n = int(input())
    A = []
    for _ in range(n):
        card = Card()
        _input = input().split(" ")
        card.suit = _input[0]
        card.value = int(_input[1])
        A.append(card)
    
    ind = dict((e, i) for i, e in enumerate(A))
    quickSort(A, 0, n-1)
    
    for i in range(n - 1):
        if A[i].value == A[i + 1].value:
            if ind[A[i]] > ind[A[i + 1]]:
                print('Not stable')
                break
    else:
        print('Stable')
    
    for i in range(n):
        print(A[i].suit, A[i].value)
             
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())
S = []
for _ in range(n):
    a, b = map(str, input().split())
    S.append([a, int(b)])
copyS = copy.deepcopy(S)

quicksort(S, 0, n-1)

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

Solution (Python):
import sys


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


SENTINEL_NUM = 10 ** 9 + 1
cnt = 0
sentinel = Card(None, SENTINEL_NUM)


def merge(A, left, mid, right):
    global cnt
    global sentinel
    n1 = mid - left
    n2 = right - mid
    L = A[left:mid] + [sentinel]
    R = A[mid:right] + [sentinel]

    i, j = 0, 0
    for k in range(left, right):
        cnt += 1
        if L[i].value <= R[j].value:
            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)


def partition(A, p, r):
    x = A[r].value
    i = p - 1
    for j in range(p, r):
        if A[j].value <= 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())
A = [[None] * 2 for _ in range(n)]
B = [[None] * 2 for _ in range(n)]
for i in range(n):
    suit, value = input().split()
    A[i] = B[i] = Card(suit, int(value))

quick_sort(A, 0, n - 1)
merge_sort(B, 0, n)

if A == B:
    print("Stable")
else:
    print("Not stable")
for i in range(n):
    print(A[i].suit, A[i].value)

Solution (Python):
from copy import copy


class Card:

    def __init__(self, s):
        splited = s.split(' ')
        self.suit = splited[0]
        self.number = int(splited[1])

    def __gt__(self, other):
        return self.number > other.number

    def __ge__(self, other):
        return self.number >= other.number

    def __le__(self, other):
        return self.number <= other.number

    def __lt__(self, other):
        return self.number < other.number

    def __repr__(self):
        return '{} {}'.format(self.suit, self.number)

    def __str__(self):
        return self.__repr__()

    def __eq__(self, other):
        return self.suit == other.suit and self.number == other.number


s = 'A 0'
SENTINEL = Card(s)
SENTINEL.number = float('inf')


def main():
    n = int(input())
    cs_1 = [Card(input()) for _ in range(n)]
    cs_2 = copy(cs_1)
    merge_sort(cs_1, n, 0, n)
    quick_sort(cs_2, 0, n-1)
    if all([c1 == c2 for c1, c2 in zip(cs_1, cs_2)]):
        print('Stable')
    else:
        print('Not stable')
    print('\n'.join([str(c) for c in cs_2]))


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 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 merge_sort(A, n, left, right):
    if left+1 < right:
        mid = (left+right) // 2
        merge_sort(A, n, left, mid)
        merge_sort(A, n, mid, right)
        merge(A, n, left, mid, right)


def merge(A, n, left, mid, right):
    L = A[left:mid]
    R = A[mid:right]
    L.append(SENTINEL)
    R.append(SENTINEL)
    i = j = 0
    for k in range(left, right):
        if L[i] <= R[j]:
            A[k] = L[i]
            i += 1
        else:
            A[k] = R[j]
            j += 1


if __name__ == "__main__":
    main()

Solution (Python):
import copy

INFTY=1000000000
def merge(A,left,mid,right):
    n1=mid-left
    n2=right-mid
    L=[ A[left+i] for i in range(n1)]
    R=[ A[mid+i] for i in range(n2)]
    L.append((INFTY,INFTY))
    R.append((INFTY,INFTY))
    i=0
    j=0
    for k in range(left,right):
        if int(L[i][1])<=int(R[j][1]):
            A[k]=L[i]
            i+=1
        else:
            A[k]=R[j]
            j+=1
    return right-left

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

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)

n=int(input())
A=[input().split() for _ in range(n)]
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(A[i]))

Solution (Python):
class Card():
    def __init__(self, suit: chr, number: int):
        self.suit = suit
        self.number = number

def partition(a: list, left: int, right: int) :
    std = a[right].number
    j = left - 1
    for i, v in enumerate(a[left:right]):
        idx = i + left
        if a[idx].number <= std:
            j += 1
            a[j], a[idx] = a[idx], a[j]

    j += 1
    a[j], a[right] = a[right], a[j]
    return j

def quick_sort(a: list, left: int, right: int):
    if left < right:
        sep = partition(a, left, right)
        quick_sort(a, left, sep-1)
        quick_sort(a, sep+1, right)

def merge(a: list, left: int, mid: int, right: int):
    n1 = mid - left
    n2 = right - mid

    L = []
    R = []
    for i in range(n1):
        L.append(a[left+i])
    for i in range(n2):
        R.append(a[mid+i])

    inf = 1 << 32
    L.append(Card("Z", inf))
    R.append(Card("Z", inf))

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

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

def is_stable(m, q):
    for i, j in zip(m, q):
        if i.number != j.number or i.suit != j.suit:
            return False
    return True

n = int(input())

cards = []
for i in range(n):
    card_info = input().split(" ")
    cards.append(Card(card_info[0], int(card_info[1])))

merge_sorted = cards.copy()
quick_sorted = cards.copy()

merge_sort(merge_sorted, 0, len(merge_sorted))
quick_sort(quick_sorted, 0, len(quick_sorted) - 1)
stable = is_stable(merge_sorted, quick_sorted)

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

for c in quick_sorted:
    print("{} {}".format(c.suit, c.number))

Solution (Python):
import sys
def t(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 k(A,p,r):
 if p<r:q=t(A,p,r);k(A,p,q-1);k(A,q+1,r)
def s(A):
 for i in range(n-1):
  if A[i][1]==A[i+1][1]and A[i][2]>A[i+1][2]:return'Not s'
 return'S'
n=int(input())
A=[(e[0],int(e[2:]),i)for i,e in enumerate(sys.stdin)]
k(A,0,n-1)
print(s(A)+'table')
print('\n'.join(f'{a} {b}'for a,b,_ in A))

Solution (Python):
import copy
from typing import List, Tuple


def partition(elements: List[Tuple[str, int]], start_idx: int, pivot_idx: int) -> int:
    pivot = elements[pivot_idx][1]
    i = start_idx - 1

    for j in range(start_idx, pivot_idx):
        if elements[j][1] <= pivot:
            i += 1
            elements[i], elements[j] = elements[j], elements[i]
    elements[i + 1], elements[pivot_idx] = elements[pivot_idx], elements[i + 1]

    return i + 1


def quick_sort(elements: List[Tuple[str, int]], p: int, r: int) -> None:
    if p < r:
        q = partition(elements, p, r)
        quick_sort(elements, p, q - 1)
        quick_sort(elements, q + 1, r)


if __name__ == "__main__":
    n = int(input())
    elements = [("", 0)] * n
    for i in range(n):
        element = input().split()
        elements[i] = (element[0], int(element[1]))

    elements_copy = copy.deepcopy(elements)
    quick_sort(elements, 0, n - 1)

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

    for elem in elements:
        print(f"{elem[0]} {elem[1]}")

Solution (Python):
class Card:
    suit = ''
    value = 0

    def __init__(self, val):
        self.suit = val[0]
        self.value = int(val[1])

    def __lt__(self, rhv):
        return self.value < rhv.value

    def __le__(self, rhv):
        return self.value <= rhv.value

    def __eq__(self, rhv):
        return self.suit == rhv.suit and self.value == rhv.value

    def __ne__(self, rhv):
        return not (self == rhv)

    def __str__(self):
        return '%s%d'%(self.suit, self.value)

def merge(arr, length, left, mid, right):



    L = arr[left : mid]
    R = arr[mid : right]

    L.append(Card([' ', 2000000000]))
    R.append(Card([' ', 2000000000]))

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

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

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

def quick_sort(arr, length, left, right):
    if (left < right):
        q = partition(arr, left, right)
        quick_sort(arr, length, left, q - 1)
        quick_sort(arr, length, q + 1, right)

if __name__ == '__main__':
    n = int(input())

    arr1 = []
    arr2 = []

    for i in range(n):
        temp = input().split(' ')
        arr1.append(Card(temp))
        arr2.append(Card(temp))
    
    stable = True

    merge_sort(arr1, n, 0, n)
    quick_sort(arr2, n, 0, n - 1)

    for i in range(n):
        if (arr1[i].suit != arr2[i].suit):
            stable = False
            break
    if stable:
        print('Stable')
    else:
        print('Not stable')

    for i in arr2:
        print('%s %d'%(i.suit, i.value))

Solution (Python):
from enum import Enum
from queue import Queue
import collections

import sys
import math

BIG_NUM = 2000000000
MOD = 1000000007
EPS = 0.000000001

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

def isStable(A):
    for i in range(1,len(A)):
        if A[i-1][1] == A[i][1]:
            if A[i-1][2] > A[i][2]:
                return 'Not stable'
    return 'Stable'

n = int(input())
A = []
for i in range(n):
    suit,num = sys.stdin.readline().split()
    A += [[suit,int(num),i]]
QuickSort(A,0,n-1)
print(isStable(A))
for i in A:
    print(i[0],i[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 = 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):
    L=A[left:mid]+[["X",10000000000]]
    R=A[mid:right]+[["X",10000000000]]
    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):
    mid=0
    if left+1 < right:
        mid = int((left + right)/2)
        mergeSort(A, left, mid)
        mergeSort(A, mid, right)
        merge(A, left, mid, right)
import copy
n=int(input())
A=[]
for i in range(n):
    Astr=input().split( )
    A.append([Astr[0],int(Astr[1])])

B=A.copy()



quickSort(A,0,n-1)

mergeSort(B,0,n)

flag=0
for i in range(n):
    if A[i]!=B[i]:
        flag=1
        break
    else:
        pass
if flag==1:
    print("Not stable")
else:
    print("Stable")



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

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


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


n = int(input())
arr = [input().split() for _ in range(n)]
arr_s = sorted(arr, key=lambda x:x[1])
quicksort(arr, 0, n - 1)


print("Stable" if arr == arr_s else "Not stable")
for ele in arr:
    print(*ele)

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)


def main():
    n = int(input())
    A = []
    for i in range(n):
        m, s = input().split()
        s = int(s)
        A.append([m, s])
    B = A[:]
    quicksort(B, 0, n-1)

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

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


if __name__ == '__main__':
    main()

Solution (Python):
def partition(A,p,r):
  q = p
  for i in range(p,r):
    if A[i][1] <= A[r][1]:
      A[q],A[i] = A[i],A[q]
      q += 1

  A[q],A[r] = A[r],A[q]
  return q

def quicksort(A,left,right):
  if left < right:
    q = partition(A,left,right)
    quicksort(A,left,q-1)
    quicksort(A,q+1,right)

def check_stable(A):
  for i in range(1,len(A)):
    if A[i-1][1] == A[i][1]:
      if A[i-1][2] > A[i][2]:
        return "Not stable"
  return "Stable"

n = int(input())
data = []
for i in range(n):
  mark, num = map(str,input().split())
  data += [[mark,int(num),i]]

quicksort(data,0,len(data) -1)
print(check_stable(data))

for line in data:
  print(line[0],line[1])

Solution (Python):
def partition(A, p, r):
    COLUMN_SORT = 1

    global flag_stable

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

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

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

    for i in range(q + 1, r):
        if A[r] > A[i]:
            flag_stable = False

    return q


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())

list_card = []
for _ in range(n):
    suit, num = input().split()
    list_card.append([suit, int(num)])



flag_stable = True

quicksort(list_card, 0, n-1)



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

for card in list_card:
    print(*card)

Solution (Python):
def merge(A, left, mid, right):
    count = 0
    INF = 1000000000000000000000
    n1 = mid - left
    n2 = right - mid

    L = [A[left+i] for i in range(n1)]
    R = [A[mid+i] for i in range(n2)]
    L.append((INF, INF))
    R.append((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 merge_sort(A, left, right):
    if left+1 < right:
        mid = (left + right) // 2
        count_left = merge_sort(A, left, mid)
        count_right = merge_sort(A, mid, right)
        count = merge(A, left, mid, right)
        return count + count_right + count_left
    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 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():
    import copy
    n = int(input())
    A = []
    for _ in range(n):
        a, b = input().split()
        A.append((a, int(b)))

    B = copy.deepcopy(A)

    merge_sort(B, 0, len(B))
    quick_sort(A, 0, n-1)

    

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

    for a in A:
        print(f"{a[0]} {a[1]}")

if __name__ == "__main__":
    main()

Solution (Python):
n = int(input())

A = []
B = []

for i in range(n):
    arr = input().split()
    A.append(arr)
    B.append(arr)

def merge(A, left, mid, right):
    n1 = mid - left
    n2 = right - mid
    L = [['x', 0]] * (n1 + 1)
    R = [['x', 0]] * (n2 + 1)

    for i in range(n1):
        L[i] = A[left + i]
    for i in range(n2):
        R[i] = A[mid + i]
    L[n1][1] = 1.0e+9 + 1
    R[n2][1] = 1.0e+9 + 1
    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 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 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 = 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(A, 0, n-1)
mergeSort(B, 0, n)

stable = True
for i in range(n):
    if A[i] != B[i]:
        stable = False

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

for i in range(n):
    print("{} {}".format(A[i][0], A[i][1]))