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, key=lambda x: x):
    x = key(A[r])
    i = p - 1

    for j in range(p, r):
        if key(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 quick_sort(A, p, r, key=lambda x: x):
    if p < r:
        q = partition(A, p, r, key=key)
        quick_sort(A, p, q - 1, key=key)
        quick_sort(A, q + 1, r, key=key)


if __name__ == '__main__':
    n = int(input())
    A = []
    for _ in range(n):
        egara, number = input().split()
        A.append((egara, int(number)))
    
    stable_sorted = sorted(A, key=lambda x: x[1])
    quick_sort(A, 0, n - 1, key=lambda x: x[1])

    if stable_sorted == A:
        print('Stable')
    else:
        print('Not stable')
    
    for egara, number in A:
        print(egara, number)

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

    def __eq__(self, other):
        if other is None or not isinstance(other, Card):
            return False
        return self.__dict__ == other.__dict__

    def __ne__(self, other):
        return not self.__eq__(other)


def partition(array, start, end):
    end_val = array[end].num
    left_end = start - 1
    for search_idx in range(start, end):
        if array[search_idx].num <= end_val:
            left_end += 1
            array[left_end], array[search_idx] = array[search_idx], array[left_end]
    array[left_end + 1], array[end] = array[end], array[left_end + 1]
    return left_end + 1


def quicksort(array, start, end):
    if start < end:
        pivot_index = partition(array, start, end)
        quicksort(array, start, pivot_index - 1)
        quicksort(array, pivot_index + 1, end)


def mergesort(array, n):
    if n <= 1:
        return array
    left_end = n // 2
    left_sorted = mergesort(array[:left_end], left_end) + [Card(10**9, None)]
    right_sorted = mergesort(array[left_end:], n - left_end) + [Card(10**9, None)]
    left_idx, right_idx = 0, 0
    idx = 0
    sorted_list = [None] * n
    while idx < n:
        if left_sorted[left_idx].num <= right_sorted[right_idx].num:
            sorted_list[idx] = left_sorted[left_idx]
            left_idx += 1
        else:
            sorted_list[idx] = right_sorted[right_idx]
            right_idx += 1
        idx += 1
    return sorted_list


def main():
    n = int(input())
    cards = []
    for _ in range(n):
        mark, number = input().split(" ")
        cards.append(Card(int(number), mark))
    mergesorted_cards = mergesort(cards, n)
    quicksort(cards, 0, n - 1)
    message = "Stable"
    for i in range(n):
        if mergesorted_cards[i] != cards[i]:
            message = "Not stable"
    print(message)
    for i in range(n):
        print("{} {}".format(cards[i].mark, cards[i].num))


if __name__ == "__main__":
    main()

Solution (Python):


def partition(A, p, r):
    x = A[r][0]
    i = p - 1
    for j in range(p, r):
        if A[j][0] <= 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 = []
valset = set({})
for i in range(n):
    c, d = input().split()
    A.append((int(d), i, c))
    valset.add(int(d))

quicksort(A, 0, n - 1)


is_stable = True
for val in valset:
    tp = [A[j][1] for j in range(n) if A[j][0] == val]
    flag = False
    for j in range(len(tp) - 1):
        if tp[j] > tp[j + 1]:
            flag = True
            break
    
    if flag:
        is_stable = False
        break
    
if is_stable:
    print("Stable")
else:
    print("Not stable")

for tp in A:
    print("{} {}".format(tp[2], tp[0]))

Solution (Python):
n=int(input())
a=[]
for i in range(n):
	x,y=input().split()
	a.append([int(y),x])
from copy import copy
b=copy(a)

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

def Merge(A, left, mid, right):
	n1 = mid - left
	n2 = right - mid
	L=[[0,"ST"]for _ in range(n1+1)]
	R=[[0,"ST"]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][0] = 10**10
	R[n2][0] = 10**10
	i = 0
	j = 0
	for k in range(left,right):
		if L[i][0] <= R[j][0]:
			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)
MergeSort(a,0,n)
Quick(b,0,n-1)
print("Stable" if a==b else "Not stable")
for i in range(n):
	print(b[i][1],b[i][0])

Solution (Python):


import copy

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



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])
    L.append(Card("", 2000000000))
    R.append(Card("", 2000000000))
    
    i = 0
    j = 0
    
    for k in range(left, right):
        if L[i].value <= R[j].value:
            A[k] = L[i]
            i += 1
        else:
            A[k] = R[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 = A[r - 1].value
    i = p - 1
    for j in range(p, r - 1):
        if A[j].value <= x:
            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:
        q = partition(A, p, r)
        quickSort(A, p, q)
        quickSort(A, q + 1, r)
    return
    
    

n = int(input())
A = []
for i in range(n):
    tmp = list(input().split())
    A.append(Card(tmp[0], int(tmp[1])))

B = copy.copy(A)
flg = True

quickSort(A, 0, n)
mergeSort(B, 0, n)

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

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, *D = open(0).read().split()
n = int(n)
A = [(D[2 * i], int(D[2 * i + 1]), i) for i in range(n)]
quicksort(A, 0, n - 1)
stable = True
for i in range(n-1):
    if A[i][1] == A[i + 1][1] and A[i][2] > A[i + 1][2]:
        stable = False
print('Stable' if stable else 'Not stable')
A = [(a[0], a[1]) for a in A]
print('\n'.join(map(lambda x: ' '.join(map(str, x)), A)))

Solution (Python):
import heapq
from collections import deque
from enum import Enum
import sys
import math
from _heapq import heappush, heappop
import copy

BIG_NUM = 2000000000
HUGE_NUM = 99999999999999999
MOD = 1000000007
EPS = 0.000000001



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):
import copy
import sys

def partition(A, p, r):
    key = A[r][1]
    i = p
    for j in range(p, r):
        
        if A[j][1] <= key:
            A[i], A[j] = A[j], A[i]
            i += 1
    
    A[r], A[i] = A[i], A[r]
    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] + [(0, sys.maxsize)]
    R = A[mid: right] + [(0, sys.maxsize)]
    i = j = 0
    k = left
    while k < right:
        if L[i][1] <= R[j][1]:
            A[k] = L[i]
            i += 1
        else:
            A[k] = R[j]
            j += 1
        k += 1

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


if __name__ == '__main__':
    n = int(input())
    numlist = []
    for _ in range(n):
        datas = input().split(' ')
        numlist.append((datas[0], int(datas[1])))
    list2 = copy.deepcopy(numlist)
    quick_sort(numlist, 0, n - 1)
    merge_sort(list2, 0, n)
    if list2 == numlist:
        print('Stable')
    else:
        print('Not stable')
    for c, num in numlist:
        print('%s %d' % (c, num))

Solution (Python):
import sys

sys.setrecursionlimit(10 ** 6)
int1 = lambda x: int(x) - 1
p2D = lambda x: print(*x, sep="\n")

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

    if p < r:
        q = Partition(aa, p, r)
        QuickSort(aa, p, q - 1)
        QuickSort(aa, q + 1, r)

def main():
    n = int(input())
    
    cc=[]
    ctoi={}
    for i in range(n):
        m,a=input().split()
        c=(int(a),m)
        ctoi[c]=i
        cc.append(c)
    QuickSort(cc,0,n-1)
    stable=True
    for c0,c1 in zip(cc,cc[1:]):
        if c0[0]==c1[0] and ctoi[c0]>ctoi[c1]:
            stable=False
            break
    print("Stable") if stable else print("Not stable")
    for c in cc:
        print(c[1],c[0])

main()

Solution (Python):

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

    def __str__(self):
        return self.suit + ' ' + str(self.value)


""" merge_sort """

def merge(A, n, left, mid, right):
    L = A[left:mid]
    R = A[mid:right]

    L.append(Card('None', 2000000000))  
    R.append(Card('None', 2000000000))

    
    i, j = 0, 0

    
    

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


""" quick_sort """

def partition(A, n, 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, n, p, r):
    if p < r:
        q = partition(A, n, p, r)
        quick_sort(A, n, p, q-1)
        quick_sort(A, n, q+1, r)


N = int(input())
A = []
for i in range(N):
    suit, value = input().split()
    value = int(value)
    A.append(Card(suit, value))
B = list(A)

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

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

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

for a in A:
    print(a)

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())
data=[]
for i in range(n):
    mark,num=map(str,input().split())
    data.append([mark,int(num)])

data_copy=copy.deepcopy(data)
data_copy=sorted(data_copy, key=lambda x:x[1])

quickSort(data,0,n-1)

print("Stable" if data==data_copy else "Not stable")

for mark,num in data:print(mark,num)

Solution (Python):
import copy

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

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

 
n=int(input())
a=[]
for i in range(n):
    a.append(input().split())
    
b=copy.deepcopy(a)
quicksort(b,1,n)
flag=True
for j in range(n-1):
    if int(b[j][1]) == int(b[j+1][1]): 
        if a.index(b[j]) > a.index(b[j+1]):flag=False ;break
if flag:print('Stable')
else:print('Not stable')

for i in b:
    print(*i)

Solution (Python):
n = int(input())
cL = []
for i in range(n):
    inputS = input()
    inputL = inputS.split()
    cL.append([inputS, int(inputL[1])])

def partition(A, l, r):
    pivot = A[r][1]
    minVI = l-1
    i = l
    while i < r:
        if A[i][1] <= pivot:
            minVI+=1
            A[i], A[minVI] = A[minVI], A[i]
        i+=1
    A[minVI+1], A[i] = A[i], A[minVI+1]
    return minVI+1

def quickSort(A, l, r):
    if l < r:
        pivotI = partition(A, l, r)
        quickSort(A, l, pivotI-1)
        quickSort(A, pivotI+1, r)

def merge(l, r):
    lI = 0
    rI = 0
    newL = []
    while lI < len(l) and rI < len(r):
        if l[lI][1] <= r[rI][1]:
            newL.append(l[lI])
            lI+=1
        else:
            newL.append(r[rI])
            rI+=1
    while lI < len(l):
        newL.append(l[lI])
        lI+=1
    while rI < len(r):
        newL.append(r[rI])
        rI+=1
    return newL

def mergeSort(curL):
    if len(curL) <= 1:
        return curL
    else:
        mid = len(curL)//2
        left = mergeSort(curL[:mid])
        right = mergeSort(curL[mid:])
        return merge(left, right)

mergeSorted = mergeSort(cL)
quickSort(cL, 0, len(cL)-1)
quickSorted = cL
if mergeSorted == quickSorted:
    print('Stable')
else:
    print('Not stable')
for v in quickSorted:
    print(v[0])

Solution (Python):
class Card:
    def __init__(self, name, number):
        self.name = name
        self.number = number

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

    def __str__(self):
        return f'{self.name} {self.number}'


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


def quick_sort(arr, l, r):
    if l >= r:
        return
    q = partition(arr, l, r)
    quick_sort(arr, l, q - 1)
    quick_sort(arr, q + 1, r)


if __name__ == '__main__':
    n = int(input())
    arr = []
    for _ in range(n):
        name, number = input().split()
        arr.append(Card(name, int(number)))
    sort_before_record = {}
    for ele in arr:
        if ele.number in sort_before_record:
            sort_before_record[ele.number].append(ele.name)
        else:
            sort_before_record[ele.number] = [ele.name]

    quick_sort(arr, 0, n - 1)

    sort_after_record = {}
    for ele in arr:
        if ele.number in sort_after_record:
            sort_after_record[ele.number].append(ele.name)
        else:
            sort_after_record[ele.number] = [ele.name]
    flag = True

    for key in sort_before_record:
        if sort_before_record[key] != sort_after_record[key]:
            flag = False
            break

    if flag:
        print('Stable')
    else:
        print('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
            m=A[i]
            A[i]=A[j]
            A[j]=m
    m=A[i+1]
    A[i+1]=A[r]
    A[r]=m
    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 _ in range(n):
    card=input().split()
    A.append([card[0],int(card[1])])
Acopy=A.copy()
quicksort(A,0,n-1)
ans="Stable"
for i in range(n-1):
    if A[i][1]==A[i+1][1]:
        if Acopy.index(A[i+1])<Acopy.index(A[i]):
            ans="Not stable"
            break
print(ans)
for i in range(n):
    print(*A[i])

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 - 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 = [None for i 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")

ans = [str(x[0]) +" "+str(x[1]) for x in A]
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
            temp=a[i]
            a[i]=a[j]
            a[j]=temp
    temp=a[i+1]
    a[i+1]=a[r]
    a[r]=temp
    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)


r=int(input())
a=[list(input().split()) for _ in range(r)]
for i in range(r):
    a[i][1]=int(a[i][1])
import copy
b=copy.deepcopy(a)
b.sort(key=lambda x:x[1])
quicksort(a,0,r-1)


if a==b:
    print("Stable")
else:
    print("Not stable")

for i in range(r):
    print(a[i][0],a[i][1])

Solution (Python):
n = int(input())
A = [input().split(" ") for _ in range(n)]
S = A.copy()

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)

SENTINEL = 9999999999999

def merge(S, n, left, mid, right):
    global SENTINEL
    n1 = mid - left
    n2 = right - mid
    L = S[left:mid] + [[" ", SENTINEL]]
    R = S[mid:right] + [[" ", SENTINEL]]
    i = j = 0
    for k in range(left, right):
        if int(L[i][1]) <= int(R[j][1]):
            S[k] = L[i]
            i += 1
        else:
            S[k] = R[j]
            j += 1

def mergeSort(S, n, left, right):
    if left + 1 < right:
        mid = int((left + right) / 2)
        mergeSort(S, n, left, mid)
        mergeSort(S, n, mid, right)
        merge(S, n, left, mid, right)

quickSort(A, 0, n-1)
mergeSort(S, n, 0, n)

def Judge():
    for _ in range(n):
        if A[_] != S[_]:
            return "Not stable"
    return "Stable"
    
print(Judge())
for _ in range(n):
    print(*A[_])

Solution (Python):
def merge(A, l, m, r):
  L = A[l:m]
  L.append((1e10, None))
  R = A[m:r]
  R.append((1e10, None))
  i, j = 0, 0
  for k in range(l, r):
    if L[i][0] <= R[j][0]:
      A[k] = L[i]
      i += 1
    else:
      A[k] = R[j]
      j += 1

def msort(A, l, r):
  if r-l > 1:
    m = (l+r)//2
    msort(A, l, m)
    msort(A, m, r)
    merge(A, l, m, r)

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

def qsort(A, l, r):
    if r-l > 1:
        q = partition(A, l, r)
        qsort(A, l, q)
        qsort(A, q+1, r)

N = int(input())
A, B = [], []
for _ in range(N):
    c, n = input().split()
    n = int(n)
    A.append((n, c))
    B.append((n, c))
qsort(A, 0, N)
msort(B, 0, N)
print('Stable' if A == B else 'Not stable')
for n, c in A:
    print(c, n)

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

n = int(input())

A = [None for _ in range(n)]
M = [None for _ in range(n)]
for i in range(n):
    tmp = list(input().split())
    A[i] = [tmp[0], int(tmp[1])]
    M[i] = [tmp[0], int(tmp[1])]


SENTINEL = 1000000005
merge_count = 0


def main():
    
    quickSort(A, 1, len(A) - 1)
    
    mergeSort(M, 0, len(M))
    

    print(isStable(A, M))
    for a in A:
        print(a[0] + ' ' + str(a[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 partition(A, p, r):
    last = A[r][1]
    i = p - 1
    
    
    for j in range(i, r, 1):
        
        if A[j][1] <= last:
            
            tmp = A[i]
            A[i] = A[j]
            A[j] = tmp
            i += 1

        
    tmp = A[i]
    A[i] = A[r]
    A[r] = tmp

    return i


def merge(M, left, mid, right):
    
    
    
    global merge_count

    L = M[left:mid] + [["SENTINEL", SENTINEL]]
    R = M[mid:right] + [["SENTINEL", SENTINEL]]

    
    

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

    
    


def mergeSort(M, left, right):
    
    

    if left + 1 < right:
        mid = (left + right) // 2
        
        mergeSort(M, left, mid)
        mergeSort(M, mid, right)
        merge(M, left, mid, right)


def isStable(A, M):
    for i in range(len(A)):
        if A[i] != M[i]:
            return "Not stable"
    return "Stable"


if __name__ == '__main__':
    main()

Solution (Python):
"""
クイックソート

6
D 3
H 2
D 1
S 3
D 2
C 1
"""
import copy

MAX = 500000
L = [None] * int(MAX / 2 + 2) 
R = [None] * int(MAX / 2 + 2) 

SENTINEL = "2000000000000"
from pprint import pprint

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

def partition(A, n, p, r):
    
    x = A[r].num
    i = p
    
    for k in range(p, r+1):
        if A[k].num <= x:
            tmp = A[i]
            A[i] = A[k]
            A[k] = tmp
            i += 1
            
    return i-1

def merge(B, n, left, mid, right):
    n1 = mid - left
    n2 = right - mid
    for i in range(n1):
        L[i] = B[left + i]
    for i in range(n2):
        R[i] = B[mid + i]
    L[n1] = Card("dummy {}".format(SENTINEL))
    R[n2] = Card("dummy {}".format(SENTINEL))
    i = 0
    j = 0
    k = left
    while  k < right:
        if L[i].num <= R[j].num:
            B[k] = L[i]
            i += 1
        elif L[i].num > R[j].num:
            B[k] = R[j]
            j += 1
        k += 1


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

            

class Card:
    def __init__(self, mark_num):
        self.mark_num = mark_num
        self.num = int(mark_num.split()[1])


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

    B = copy.deepcopy(A)

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

    for i in range(n):
        if A[i].mark_num != B[i].mark_num:
            print("Not stable")
            break
    else:
        print("Stable")
        

    for a in A:
        print(a.mark_num)

Solution (Python):
INF = 1000000000

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

	def __repr__(self):
		return self.suit + ' ' + str(self.value)


def partition(A, p, r):
	x = A[r]
	i = p - 1
	for j in range(p, r):
		if A[j].value <= x.value:
			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]
	R = A[mid:right]
	L.append(Card("INF", INF))
	R.append(Card("INF", INF))
	i = 0
	j = 0
	for k in range(left, right):
		if L[i].value <= R[j].value:
			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)


if __name__ == "__main__":
	n = int(input())
	A = []
	for _ in range(n):
		suit, value = input().split()
		A.append(Card(suit, int(value)))

	B = A.copy()
	quickSort(A, 0, n - 1)
	mergeSort(B, 0, n)
	if A == B:
		print("Stable")
	else:
		print("Not stable")
	for card in A:
		print(card)

Solution (Python):
def merge(A, left, mid , right):
  L = A[left:mid]
  R = A[mid:right]
  L.append(('J', 1000000001))
  R.append(('J', 1000000001))
  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 merge_sort(A, p ,r):
  if p + 1 < r:
    m = (p + r) // 2
    merge_sort(A, p, m)
    merge_sort(A, m, r)
    merge(A, p, m, r)

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

cards = []

for i in range(n):
  card, rank = input().split(" ")
  cards.append((card, int(rank)))
copy_cards = cards[:]

quick_sort(cards, 0, len(cards) - 1)
merge_sort(copy_cards, 0, len(cards))

stable = True
for x, y in zip(cards, copy_cards):
  if x != y:
    stable = False
    print('Not stable')
    break

if stable:
  print('Stable')

for card in cards:
  print("{} {}".format(card[0], card[1]))

Solution (Python):
def partition(A, p, r):
    x = A[r][1]
    i = p - 1
    for j in range(p, r + 1):
        if A[j][1] <= x:
            i += 1
            A[i], A[j] = A[j], 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 makedic(A, n):
    d = {}
    for i in range(n):
        key = A[i][1]
        value = A[i][0]
        if key in d:
            d[key] += value
        else:
            d[key] = value
    return d

def main():
    N = int(input())
    A = []
    for i in range(N):
        a, v = input().split()
        v = int(v)
        A.append((a, v))

    sd = makedic(A, N)
    quicksort(A, 0, N - 1)
    ed = makedic(A, N)

    print('Stable' if sd == ed else 'Not stable')

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

if __name__ == '__main__':
    main()

Solution (Python):
import copy

class Cards:
    def __init__(self, letter, value):
        self.letter = letter
        self.value = value

def Partition(NUM_LIST, left, right):
    v = NUM_LIST[right-1].value
    border = left
    for foot in range(left, right-1):
        if NUM_LIST[foot].value <= v:
            NUM_LIST[foot], NUM_LIST[border] = NUM_LIST[border], NUM_LIST[foot]
            border += 1
    NUM_LIST[right-1], NUM_LIST[border] = NUM_LIST[border], NUM_LIST[right-1]
    return border
    
def QuickSort(NUM_LIST, left, right):
    if left+1 < right:
        q = Partition(NUM_LIST, left, right)
        QuickSort(NUM_LIST, left, q)
        QuickSort(NUM_LIST, q+1, right)

def MergeSort(NUM_LIST, left, right):
    if left+1 < right:
        mid = (left+right)//2
        MergeSort(NUM_LIST, left, mid)
        MergeSort(NUM_LIST, mid, right)
        Merge(NUM_LIST, left, mid, right)

def Merge(NUM_LIST, left, mid, right):
    L = NUM_LIST[left:mid]
    inf = Cards("inf", 1000000001)
    L.append(inf)
    R = NUM_LIST[mid:right]
    R.append(inf)
    i=0
    j=0
    for k in range(left, right):
        if L[i].value > R[j].value:
            NUM_LIST[k] = R[j]
            j += 1
        else:
            NUM_LIST[k] = L[i]
            i += 1

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

for i in range(n):
    c, v = input().split()
    v = int(v)
    tmp = Cards(c, v)
    CARD_LIST.append(tmp)

QUICK_LIST = copy.copy(CARD_LIST)
MERGE_LIST = copy.copy(CARD_LIST)

QuickSort(QUICK_LIST, 0, len(QUICK_LIST))
MergeSort(MERGE_LIST, 0, len(MERGE_LIST))


if QUICK_LIST == MERGE_LIST:
    print("Stable")
else:
    print("Not stable")
    
for i in range(len(MERGE_LIST)):
    print("%s %d"%(QUICK_LIST[i].letter, QUICK_LIST[i].value))