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 = 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 stable(A, B):
    for i in range(len(A)):
        if A[i] != B[i]:
            return "Not stable"
    return "Stable"

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([0, 10**9])
    R.append([0, 10**9])

    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)

n = int(input())
X = []
for i in range(n):
    a = input().split()
    X.append([a[0], int(a[1])])
    
Y = X[:]
quicksort(X, 0, n-1)
mergeSort(Y, 0, n)
print(stable(X, Y))
for elem in X:
    print(" ".join(map(str, elem)))

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


n = int(input())
A = []
for i in range(n):
    a, b = input().split()
    A.append((a, int(b)))
dct0 = {}
for a in A:
    dct0[a[1]] = []
for a in A:
    dct0[a[1]].append(a[0])
quick_sort(A, 0, n)
dct1 = {}
for a in A:
    dct1[a[1]] = []
for a in A:
    dct1[a[1]].append(a[0])
if dct0 == dct1:
    print('Stable')
else:
    print('Not stable')
for a in A:
    print(*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):



class Card:
    def __init__(self):
        self.suit = ''
        self.num = 0
    def __str__(self):
        return self.suit + ' ' + str(self.num)

def merge(A, left, mid, right):
    """
    right: 最後の添字 + 1
    """
    SENTINEL = Card()
    SENTINEL.num = 2 * 10**9

    n1 = mid - left;
    n2 = right - mid;
    L = A[left:left+n1]
    R = A[mid:mid+n2]

    L.append(SENTINEL)
    R.append(SENTINEL)
    i = 0
    j = 0

    for k in range(left, right):
        if L[i].num <= R[j].num:
            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):
    """
    r: 最後の添字
    """
    x = A[r].num 
    i = p - 1
    for j in range(p, r):
        if A[j].num <= 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 = []
for i in range(n):
    x = Card()
    x.suit, x.num = input().split()
    x.num = int(x.num)
    A.append(x)

A_mergeSort = A[:]
mergeSort(A_mergeSort, 0, n)
quickSort(A, 0, n-1)
isStable = True

for i in range(n):
    if A[i].suit == A_mergeSort[i].suit and A[i].num == A_mergeSort[i].num:
        pass
    else:
        isStable = False

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

for i in A:
    print(i)

Solution (Python):
from collections import defaultdict


def key(pair):
    _, n = pair
    return n


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


def is_stable(ordered, original):
    scanned_ordered = defaultdict(list)
    scanned_original = defaultdict(list)
    for a, b in zip(ordered, original):
        s, n = a
        scanned_ordered[n].append(s)
        t, m = b
        scanned_original[m].append(t)
    for k in scanned_ordered:
        if scanned_ordered.get(k, "__NaN_1__") != scanned_original.get(k, "__NaN_2__"):
            return False
    return True


N = int(input())
A = []
for _ in range(N):
    s, n = input().split()
    A.append((s, int(n)))
sorted_A = A.copy()
quick_sort(sorted_A, 0, N - 1)
print("Stable" if is_stable(sorted_A, A) else "Not stable")
for s, n in sorted_A:
    print(s, n)

Solution (Python):


INF = 10**10

def merge(A, l, mid, r):
    a1 = A[l:mid] + [[None, INF]]
    a2 = A[mid:r] + [[None, INF]]
    i = j = 0
    for k in range(l, r):
        if a1[i][1] <= a2[j][1]:
            A[k] = a1[i]
            i += 1
        else:
            A[k] = a2[j]
            j += 1

def merge_sort(A, l, r):
    if l + 1 >= r:
        return
    mid = (l + r) // 2
    
    merge_sort(A, l, mid)
    merge_sort(A, mid, r)
    
    merge(A, l, mid, r)
    
    
def quick_sort(A, l, r):
    if l < r:
        
        mid = r
        pivot = A[mid][1]
        A[mid], A[r] = A[r], A[mid]
        i = 0
        for j in range(l, r):
            if A[j][1] <= pivot:
                A[l+i], A[j] = A[j], A[l+i]
                i += 1
        A[l+i], A[r] = A[r], A[l+i]
        
        quick_sort(A, l, l+i-1)
        quick_sort(A, l+i+1, r)

n = int(input())
cards = [input().split() for _ in range(n)]

for card in cards:
    card[1] = int(card[1])

confirm_cards  = cards[:]

quick_sort(cards, 0, n - 1)
merge_sort(confirm_cards, 0, n)

if cards == confirm_cards:
    print('Stable')
else:
    print('Not stable')
    
for card in cards:
    print(*card)

Solution (Python):
from operator import attrgetter
class Card:
    def __init__(self, suit, number):
        self.suit = suit
        self.number = number

def partition(A, p, r):
    x = A[r]
    i = p-1
    for j in range(p, r):
        if A[j].number <= x.number:
            i = i + 1
            tp = A[j]
            A[j] = A[i]
            A[i] = tp
        else:
            continue
    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 main():
    n = int(input())
    A = []
    for _ in range(n):
        suit, num = map(str, input().split())
        A.append(Card(suit, int(num))) 
    comp = sorted(A, key=attrgetter('number'))
    quickSort(A, 0, n-1)
    if A == comp:
        print('Stable')
    else:
        print('Not stable')
    for p in A:
        print(p.suit, p.number)
main()

Solution (Python):
n = int(input())
a = [0]*n


class card:
    def __init__(self, s, input_idx):
        self.m = s.split()[0]
        self.num = int(s.split()[1])
        self.t = s
        self.input_idx = input_idx
 
for i in range(n):
    a[i] = card(input(), i)
    
def partition(A, p, r):
    x = A[r].num
    i = p-1
    for j in range(p,r):
        if A[j].num <= 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)

stable = True
for i in range(1, n):
    if a[i].num==a[i-1].num and a[i].input_idx<a[i-1].input_idx:
        stable = False
        
if stable:
    print('Stable')
else:
    print('Not stable')
    
for item in a:
    print(item.t)

Solution (Python):
def partition(A, p, r):
    x = A[r][2]
    i = p - 1

    for j in range(p, r):
        if 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 IsStable(A):
    for index, a in enumerate(A):
        for i in range(index, len(A)):
            if (a[2] == A[i][2]) and (a[0] > A[i][0]):
                return "Not stable"

    return "Stable"



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

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

print(IsStable(A))
[print("{} {}".format(A[i][1], A[i][2])) for i in range(len(A))]

Solution (Python):
class Card:
    def __init__(self, mark, numebr):
        super().__init__()
        self.mark = mark
        self.number = number

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


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


if __name__ == "__main__":
    n = int(input())
    Cards = []
    Cards2 = []
    for _ in range(n):
        mark, number = input().split()
        Cards.append(Card(mark, int(number)))
        Cards2.append(Card(mark, int(number)))

    quickSort(Cards, 0, n-1)
    Cards2 = sorted(Cards2)

    stable = True
    for i in range(n):
        if not (Cards[i].mark == Cards2[i].mark and Cards[i].number == Cards2[i].number):
            stable = False

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

    for card in Cards:
        print('{} {}'.format(card.mark, card.number))

Solution (Python):
def partition(A, l, r):
    """ partition A[l:r] using q(A[r]) and return q's index
    """
    q = A[r][1]
    sep_i = l 
    for j in range(l, r):
        if A[j][1] <= q:
            
            
            
            A[sep_i], A[j] = A[j],  A[sep_i]
            sep_i += 1 
        else:
            
            pass

    A[sep_i], A[r] = A[r], A[sep_i]
    
    return sep_i

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

def is_stable(A, B):
    cA = list(A)
    for x in B:
        i = cA.index(x)
        if i == 0:
            pass
        elif cA[i - 1][1] == x[1]:
            return False
        del cA[i]
    return True

A = []
r = int(input())
for _ in range(r):
    mark, num = input().split()
    A.append([mark, int(num)])

B = list(A)
quick_sort(A, 0, r)

if is_stable(A, B):
    print('Stable')
else:
    print('Not stable')

for x in A:
    print(*x)

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

def show(l):
    for i in range(len(l)):
        print(l[i][0], l[i][1], sep = ' ')
    

n = int(input())
l_1 = []
for _ in range(n):
    a = input().split()
    l_1.append(a)
l_2 = copy.deepcopy(l_1)

quickSort(l_1, 0, n-1)

for i in range(n-1):
    if int(l_1[i][1]) == int(l_1[i+1][1]):
        if l_2.index(l_1[i]) > l_2.index(l_1[i+1]):
            print('Not stable')
            break
else:  
    print('Stable')

show(l_1)

Solution (Python):
import math
import string
import itertools
import fractions
import heapq
import collections
import re
import array
import bisect
import sys
import random
import time
inf = 10**9


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 main():
    n = int(input())
    cards = []
    for i in range(n):
        c = input().split()
        cards.append((c[0], int(c[1])))

    stable_sorted_cards = sorted(cards, key=lambda x: x[1])
    quicksort(cards, 0, n-1)

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

    for card in cards:
        print(card[0], card[1])


if __name__ == '__main__':
    main()

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 = []
for i in range(n):
    a, b = input().split()
    A.append([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):
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 += 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())
card = [input().split() for i in range(N)]
for i in range(N):
    card[i][1] = int(card[i][1])

card2 = copy.deepcopy(card)
card2.sort(key=lambda x: x[1])

quickSort(card,0,N-1)



ans = 'Stable'
for i in range(N):
    if card[i][0] != card2[i][0]:
        ans = 'Not stable'
        break
print(ans)
for i in range(N):
    print(' '.join(map(str,card[i])))

Solution (Python):


import copy

N = int(input())
lst1 = [list(input().split()) for i in range(N)]
lst2 = copy.copy(lst1)
INF = 10**9 + 1

def merge(A, left, mid, right):
    n1 = mid - left
    n2 = right - mid
    L = A[left:mid]
    L.append(("", INF))  
    R = A[mid:right]
    R.append(("", INF))  
    i, j = 0, 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

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

quick_sort(lst1, 0, N-1)
merge_sort(lst2, 0, N)
ans = 'Stable'
if (lst1 != lst2):
    ans = 'Not stable'
print(ans)
for i in lst1:
    print(*i)

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

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

def is_stable(original_list, sorted_list):
    for key, val in sorted_list:
        for original_key, original_val in original_list[:]:
            if val == original_val:
                if key != original_key:
                    print("Not stable")
                    return
                original_list.remove([original_key, original_val])
                break
    print("Stable")
    return
    
if __name__ == "__main__":
    n = int(input())
    A = [input().split() for _ in range(n)]
    A_original = deepcopy(A)
    quick_sort(0, n-1)
    is_stable(A_original, A)
    for key, val in A:
        print("{} {}".format(key, val))

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

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

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

n=int(input())
cards=[]
for i in range(n):
    suit,num=input().split()
    cards.append(card(suit,int(num),i))

quicksort(0,n-1)

stableflag=True
for i in range(1,n):
    if(cards[i-1].num == cards[i].num and cards[i-1].input_index > cards[i].input_index):
        stableflag=False
        break
if(stableflag):
    print("Stable")
else:
    print("Not stable")

for ci in cards:
    print(ci.suit,ci.num)

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
            tmp = A[i]
            A[i] = A[j]
            A[j] = tmp
    tmp = A[i+1]
    A[i+1] = A[r]
    A[r] = tmp
    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 check_stable(C1, C2):
    C_order_table = {}
    sorted_C_order_table = {}
    for i in range(len(C1)):
        if C_order_table.get(C1[i][1]):
            C_order_table[C1[i][1]] += C1[i][0]
        else:
            C_order_table[C1[i][1]] = C1[i][0]
        
        if sorted_C_order_table.get(C2[i][1]):
            sorted_C_order_table[C2[i][1]] += C2[i][0]
        else:
            sorted_C_order_table[C2[i][1]] = C2[i][0]
    
    is_stable = True
    for key in C_order_table.keys():
        if C_order_table.get(key) != sorted_C_order_table.get(key):
            is_stable = False
            break
    
    if is_stable:
        print('Stable')
    else:
        print('Not stable')
n = int(input())
A = []
for i in range(n):
    c_and_num = input().split(' ')
    c = c_and_num[0]
    num = int(c_and_num[1])
    A.append((c, num))
original_A = A.copy()
quick_sort(A, 0, n-1)
check_stable(original_A, A)
for c, num in A:
    print(c, num)

Solution (Python):
import copy

n = int(input())

Card1 = []

for i in range(n):
  Card1.append(input())

def partition(B, p, r):
  x1, x2 = B[r].split()
  global i
  i = p-1
  for j in range(p, r):
    c1, c2 = B[j].split()
    if int(c2) <= int(x2):
      i += 1
      y = B[i]
      z = B[j]
      B[i] = z
      B[j] = y
  a = B[i+1]
  b = B[r]
  B[i+1] = b
  B[r] = a
  return i+1

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

def merge(A, left, mid, right):
  inf = float('inf')
  L = A[left:mid] + ["D inf"]
  R = A[mid:right] + ["D inf"]
  i = 0
  j = 0
  for k in range(left, right):
    l1 = L[i].split()
    r1 = R[j].split()
    l2 = float(l1[1])
    r2 = float(r1[1])
    if l2 <= r2:
      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)

Card2 = copy.deepcopy(Card1)

quicksort(Card1, 0, n-1)

mergesort(Card2, 0, n)

if Card1 == Card2:
  print("Stable")
else:
  print("Not stable")

for i in range(n):
  print(Card1[i])

Solution (Python):
inf = 10000000000

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

def quick_sort(a, left, right):
    if left < right:
        q = partition(a, left, right)
        quick_sort(a, left, q)
        quick_sort(a, q + 1, right)

def merge(a, left, mid, right):
    L = a[left : mid] + [('jorker', inf)]
    R = a[mid : right] + [('jorker', inf)]
    i = 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, 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)

    

if __name__ == "__main__":
    n = int(input())
    A = [None] * n
    B = [None] * n
    for i in range(n):
        picture, number = input().split()
        A[i] = (picture, int(number))
        B[i] = (picture, int(number))
    
    quick_sort(A, 0, n)
    merge_sort(B, 0, n)

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

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

Solution (Python):
count = 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 = A[j]
            A[j] = A[i]
            A[i] = a
    a = A[i+1]
    A[i+1] = A[r]
    A[r] = a

    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):
    global count
    L = [0] * (mid - left + 1)
    R = [0] * (right - mid + 1)

    for i in range(len(L)):
        if i  == len(L) - 1:
            L[i] = ['A', float('inf')]
        else:
            L[i] = a[left+i]
    
    for i in range(len(R)):
        if i == len(R) - 1:
            R[i] = ['A', float('inf')]
        else:
            R[i] = a[mid+i]

    i = 0
    j = 0
    for k in range(left, right):
        if L[i][1] <= R[j][1]:
            a[k] = L[i]
            i += 1
        else:
            if i != len(L) - 1 and j != len(R) - 1:
                count += len(L) - i - 1
            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)

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

quicksort(A, 0, n-1)
mergeSort(A2, 0, n)

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

if flag == 1:
    print('Not stable')
else:
    print('Stable')

for i in range(n):
    print(str(A[i][0]) + ' ' + str(A[i][1]))

Solution (Python):
import copy

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

B = copy.deepcopy(A)
B.sort(key = lambda x: int(x[2:]))

quickSort(A, 0, n-1)

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

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

Solution (Python):
class Card:

    def __init__(self, data):
        self.mark = data[0]
        self.number = int(data[2:])

    def __str__(self):
        return f"{self.mark} {self.number}"

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

    def __ne__(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 __ge__(self, other):
        return self.number >= other.number

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


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


def is_stable():
    count = 0
    for i, a in enumerate(A):
        if i == len(A) - 1:
            return True
        k = 0
        for o in Origin:
            if a.number == o.number:
                if count != k:
                    k += 1
                    continue
                if a.mark != o.mark:
                    return False
                else:
                    break
        if a.number != A[i + 1].number:
            count = 0
        else:
            count += 1

A = []
n = int(input())
for i in range(n):
    A.append(Card(input()))
Origin = A.copy()
quickSort(0, len(A) - 1)
print("Stable" if is_stable() else "Not stable")
print("\n".join(str(a) for a in A))

Solution (Python):
import 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[j], A[i] = A[i], A[j]
        else:
            pass 
    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 = [[0, 0]]*(n1+1)
    for i in range(n1):
        L[i] = A[left+i]
    
    R = [[0, 0]]*(n2+1)
    for i in range(n2):
        R[i] = A[mid+i]
    
    L[n1][1] = 10000000000
    R[n2][1] = 10000000000

    i, j = 0, 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
    
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())
card = [input().split() for i in range(n)]

copy_card = copy.copy(card)
quickSort(copy_card, 0, n-1)
quick_list = copy_card

copy_card = copy.copy(card)
mergeSort(copy_card, 0, n)
merge_list = copy_card

if quick_list == merge_list:
    print('Stable')
else:
    print('Not stable')
for i in range(n):
    print(' '.join(quick_list[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 quicksort(A,p,r):
    if p < r:
        q = partition(A,p,r)
        quicksort(A,p,q-1)
        quicksort(A,q+1,r)

class checkstable:
    def __init__(self):
        self.d = {}
    def storecards(self,A):
        for i in range(len(A)):
            if A[i][1] in self.d:
                self.d[A[i][1]].append(A[i][0])
            else:
                 self.d[A[i][1]] = [(A[i][0])]

    def isstable(self,A):
        for i in range(len(A)):
            if self.d[A[i][1]].pop(0) != A[i][0]:
                      return "Not stable"
        return "Stable"

n = int(input())
A = []
for _ in range(n):
   mark,num = input().split()
   num = int(num)
   A.append([mark,num])
quick = checkstable()
quick.storecards(A)

quicksort(A,0,n - 1)
stable = quick.isstable(A)
print(stable)
for i in range(n):
   print(*A[i])