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 main():
    n = input()
    A = []
    for i in range(n):
        A.append(raw_input())
    B = A[:]
    
    quickSort(A,0,n-1)
    mergeSort(B,0,n)

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

    for item in A:
        print item


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


def merge(A,left,mid,right):
    n1 = mid - left
    n2 = right - mid
    L = [A[left+i] for i in range(n1)]
    L += ["L inf"]
    R = [A[mid+i] for i in range(n2)]
    R += ["R inf"]
    i = 0
    j = 0
    for k in range(left,right):
        if float(L[i][2:]) <= float(R[j][2:]):
            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__":
    main()

Solution (Python):
import sys


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


def isStable(A):
    for i in range(0, len(A)-1):
        if A[i][1] == A[i+1][1]:
            if A[i][2] > A[i+1][2]:
                return False
    return True

if __name__ == "__main__":
    n = int(sys.stdin.readline())
    B = []
    for i in range(n):
        c = sys.stdin.readline().split()
        B.append([c[0], int(c[1]), i])
    quickSort(B, 0, n-1)
    if isStable(B):
        print("Stable")
    else:
        print("Not stable")
    for b in B:
        print(b[0], b[1])

Solution (Python):
import sys

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

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

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

def main():
    """ ????????? """
    num = int(input().strip())
    istr = sys.stdin.read()
    cards = list(istr.splitlines())
    
    A = [[0,0] for i in range(num)]
    B = [[0,0] for i in range(num)]
    
    for i in range(num):
        A[i][0] = cards[i][0]
        A[i][1] = int(cards[i][2:])
        B[i][0] = cards[i][0]
        B[i][1] = int(cards[i][2:])

    quickSort(A, 0, num-1,1)
    B.sort(key = lambda d:d[1])
    res = "Stable"
    for i in range(num):
        if A[i][0] != B[i][0] or A[i][1] != B[i][1]:
            res = "Not stable"
            break

    print(res)
    for x in A:
        print(" ".join(map(str, x)))

if __name__ == '__main__':
    main()

Solution (Python):
import copy

n = int(raw_input())
a = [] 
        
for i in range(n):
    char, num = raw_input().split()
    num = int(num)
    a.append([char, num])

a_original = copy.copy(a)
    
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)
        
quickSort(a, 0, n-1)
for i in range(n-1):
    if a[i][1] == a[i+1][1]:
        if a_original.index(a[i]) > a_original.index(a[i+1]):
            print 'Not stable'
            break
else:
     print 'Stable'       

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

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


def partition(a, p, r):
    pivot = a[r]
    i = p-1
    for j in range(p, r):
        if compare(pivot, a[j]) >= 0:
            i += 1
            a[i], a[j] = a[j], a[i]
    a[r], a[i+1] = a[i+1], a[r]
    return i+1

def compare(a,b):
    if a[0] > b[0]:
        return 1
    elif a[0] < b[0]:
        return -1
    else:
        return 0

n = int(raw_input())
a = []
suits = {}
for _ in range(n):
    suit, number = raw_input().split(' ')
    number = int(number)
    a.append((number, suit))
    if number not in suits:
        suits[number] = []
    suits[number].append(suit)

sort(a, 0, len(a)-1)

flag = True
for number, suit in a:
    correct_suit = suits[number].pop(0)
    if suit != correct_suit:
        flag = False
        break

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

for number, suit in a:
    print suit, number

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

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

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

def isStable(a):
    length = int(len(a))
    for i in range(length):
        for j in range(i+1,length-1) :
            if a[i][1] == a[j][1] and a[i][2] > a[j][2]:
                return False
                break
    return True

if __name__ == '__main__':
    cnt = int(input())
    A = []
    for i in range(cnt):
        N = input().split()
        N.append(i)
        A.append(N)
    p = 0
    r = len(A)
    B = qsort(A,p,r)
    if isStable(B):
        print("Stable")
    else:
        print("Not stable")
    for i in B:
        print ("{0} {1}".format(i[0],i[1]))

Solution (Python):
def num(card):
    return int(card[2:])

def partition(A, p, r):
    x = num(A[r])
    i = p - 1
    for j in range(p, r):
        if num(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(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() for _ in range(n)]
B = sorted(A, key=num)
quicksort(A, 0, n - 1)

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

print(msg)
for card in A:
    print(card)

Solution (Python):
def num(card):
    return int(card[2:])

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

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

n = int(input())
A = [input() for _ in range(n)]
B = A[:]
quicksort(B, 0, n - 1)

print("Stable" if is_stable(A, B) else "Not stable")
for card in B:
    print(card)

Solution (Python):
def num(card):
    return int(card[0][2:])

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

def is_stable(A):
    for i in range(n - 1):
        if num(A[i]) == num(A[i + 1]) and A[i][1] > A[i + 1][1]:
            return False
    return True

n = int(input())
A = [(input(), i) for i in range(n)]
quicksort(A, 0, n - 1)

print("Stable" if is_stable(A) else "Not stable")
for card in A:
    print(card[0])

Solution (Python):
def swap(A,i,j):
    A[i],A[j] = A[j],A[i]
    return A

def isStable(A):
    for i in range(1, len(A)):
        if A[i][1] == A[i-1][1]:
            if A[i][2] < A[i-1][2]:
                return False
    return True

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

def quick(A,p=0,r=None):
    if r is None:
        r = len(A)-1
    if p < r:
        q = partition(A,p,r)
        quick(A,p,q-1)
        quick(A,q+1,r)

import sys
if __name__ == "__main__":
    n = int(sys.stdin.readline())
    A = []
    for i in range(n):
        card = sys.stdin.readline().split()
        A.append([card[0], int(card[1]), i])
    quick(A,0,n-1)
    if isStable(A):
        print("Stable")
    else:
        print("Not stable")
    for card in A:
        print(card[0], card[1])

Solution (Python):
n = int(input())
a = []
for i in range(n):
    suit, num = input().split()
    a.append([suit, int(num), int(i)])

b = a[:]

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 checkStable(a):
    for i in range(len(a) - 1):
        if a[i][1] == a[i + 1][1] and a[i][2] > a[i + 1][2]:
            return "Not stable"
    return "Stable"

quickSort(a, 0, n - 1)

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

Solution (Python):

import sys


class Card(object):
    def __init__(self, card):
        self._suit = card[0]
        self._value = int(card[1])

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

    def __lt__(self, other):
        if other is None:
            return False
        return self._value < other._value

    def __le__(self, other):
        if other is None:
            return False
        return self._value <= other._value

    def __gt__(self, other):
        if other is None:
            return False
        return self._value > other._value

    def __ge__(self, other):
        if other is None:
            return False
        return self._value >= other._value

    def getValue(self):
        return self._value

    def __str__(self):
        return self._suit + " " + str(self._value)


def merge(lst, left, mid, right):
    L = lst[left: mid]
    R = lst[mid: right]
    l_len = len(L)
    r_len = len(R)
    i = 0
    j = 0
    for k in range(left, right):
        if l_len <= i:
            lst[k] = R[j]
            j += 1
        elif r_len <= j:
            lst[k] = L[i]
            i += 1
        elif L[i] <= R[j]:
            lst[k] = L[i]
            i += 1
        else:
            lst[k] = R[j]
            j += 1


def mergeSort(lst, left, right):
    if left + 1 < right:
        mid = (left + right) >> 1
        mergeSort(lst, left, mid)
        mergeSort(lst, mid, right)
        merge(lst, left, mid, right)


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


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


if __name__ == "__main__":
    n = int(input())
    data = [val.split() for val in sys.stdin.readlines()]
    cards = [Card(card) for card in data]
    conf = cards[:]
    quicksort(cards, 0, n - 1)
    mergeSort(conf, 0, n)
    if cards == conf:
        print("Stable")
    else:
        print("Not stable")
    print("\n".join([str(card) for card in cards]))

Solution (Python):
'''
????????§????¢?????????????
???????????????????????????????????£????????????
???????????????????????????????????????????????????????????????
?????¢????????????????????????????????????????¢????????????°?????????
???????????????1?????§????????¢??????????????°???????????¨?????????
'''
def partition(A,p,r):
    x = A[r]
    i = p-1
    for j in range(p,r):
        if A[j][1] <= x[1]:
            i = 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,n):
    for i in range(1,n-1):
        if A[i-1][1] == A[i][1] and A[i-1][2] > A[i][2]:
            return False
    return True

if __name__ == '__main__':
    n = (int)(input())
    A = []
    for i in range(0,n):
        tmp = list(input().split())
        A.append((tmp[0],(int)(tmp[1]),i))
    quicksort(A,0,n-1)

    print("Stable" if isStable(A,n) else "Not stable" )

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

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

    return i


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


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

for i in range(n):
    char, num = raw_input().split()
    num = int(num)
    A.append([char, num])

B = list(A)

quick_sort(A, 0, n-1) 
B.sort(key=lambda x: x[1])

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

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

Solution (Python):
"""Quick Sort."""
 
def partition(A, p, r):
    """Divide list A into A[p:q] whose elements aren't greater than A[q] and
    A[q+1:r] whose elements are greater than A[q].
 
    Each element of A is a list [x, y].
    x is a character of S, H, C or D (trump suits).
    y is a natural number.
    Sorting is done based on y numbers.
     
    Default value of p is 0.
    The number as a refernce of the division is A[r].
     
    Return the index q.
    """
 
    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):
    """Sort list A in ascending order with quick sort algorithm.
 
    Default value of p is 0 (the start index).
    r is 1 less than the length of A (the last index of A).
    """
 
    if p < r:
        q = partition(A, p, r)
        quickSort(A, p, q - 1)
        quickSort(A, q + 1, r)
 
 
def is_stable(A, B):
    """Check the stability of sorted list A.
 
    A is a sorted list.
    B is a original list.
 
    Return True or False.
    """
 
    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
 
 
 
import sys
 
r = int(sys.stdin.readline()) - 1
 
A = []
 
for x in sys.stdin.readlines():
    suit, num = x.split()
    num = int(num)
    A.append([suit, num])
 
B = list (A)
 
quickSort(A, 0, r)
 
if is_stable(A, B):
    print('Stable')
else:
    print('Not stable')
 
for x in A:
    print(*x)

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

Solution (Python):


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)
    
def merge(A, left, mid, right):
    n1 = mid - left
    n2 = right - mid
    L = A[left:left+n1]
    R = A[mid:mid+n2]
    L.append([None, float('inf')])
    R.append([None, float('inf')])
    
    i = 0
    j = 0
    for k in range(left, right):
        if L[i][1] <= R[j][1]:
            A[k] = L[i]
            i += 1
        else:
            A[k] = R[j]
            j += 1

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


if __name__ == '__main__':

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

    mergeSort(A_m, 0, n)
    quickSort(A_q, 0, n-1)

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

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

Solution (Python):
INF = int(1e10)
def merge(A, left, mid, right):
    L = A[left: mid] + [[0, INF]]
    R = A[mid: right] + [[0, 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 mergeSort(A, left, right):
    if left + 1 < right:
        mid = (left + right) // 2
        mergeSort(A, left, mid)
        mergeSort(A, mid, right)
        merge(A, left, mid, right)
def partition(A, p, r):
    x = A[r][1]
    i = p - 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())
f = lambda a: (a[0], int(a[1]))
A = [f(input().split()) for _ in range(n)]
B = A[:]
mergeSort(A, 0, n)
quicksort(B, 0, n - 1)
print("Stable" if A == B else "Not stable")
print(*(f"{a} {b}" for a, b in B), sep="\n")

Solution (Python):
import sys
readline = sys.stdin.readline
INF = int(1e10)
def merge(A, left, mid, right):
    L = A[left: mid] + [[0, INF]]
    R = A[mid: right] + [[0, 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 mergeSort(A, left, right):
    if left + 1 < right:
        mid = (left + right) // 2
        mergeSort(A, left, mid)
        mergeSort(A, mid, right)
        merge(A, left, mid, right)
def partition(A, p, r):
    x = A[r][1]
    i = p - 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())
f = lambda a: (a[0], int(a[1]))
A = [f(readline().split()) for _ in range(n)]
B = A[:]
mergeSort(A, 0, n)
quicksort(B, 0, n - 1)
print("Stable" if A == B else "Not stable")
print(*(f"{a} {b}" for a, b in B), sep="\n")

Solution (Python):
import sys
readline = sys.stdin.readline
import sys
readline = sys.stdin.readline
INF = int(1e10)
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(A):
    for i in range(0, len(A) - 1):
        if A[i][1] == A[i + 1][1]:
            if A[i][2] > A[i + 1][2]:
                return False
    return True
n = int(input())
f = lambda a, i: (a[0], int(a[1]), i)
A = [f(readline().split(), i) for i in range(n)]
quicksort(A, 0, n - 1)
print("Stable" if isStable(A) else "Not stable")
print(*(f"{a} {b}" for a, b, c in A), sep="\n")

Solution (Python):
import sys
readline = 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 isStable(A):
    for i in range(0, len(A) - 1):
        if A[i][1] == A[i + 1][1]:
            if A[i][2] > A[i + 1][2]:
                return False
    return True
n = int(input())
f = lambda a, i: (a[0], int(a[1]), i)
A = [f(readline().split(), i) for i in range(n)]
quicksort(A, 0, n - 1)
print("Stable" if isStable(A) else "Not stable")
print("\n".join(f"{a} {b}" for a, b, c in A))

Solution (Python):
import sys
readline = 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 isStable(A):
    for i in range(0, len(A) - 1):
        if A[i][1] == A[i + 1][1]:
            if A[i][2] > A[i + 1][2]:
                return False
    return True
n = int(input())
f = lambda a: (a[0], int(a[1]))
A = [f(readline().split()) + (i,) for i in range(n)]
quicksort(A, 0, n - 1)
print("Stable" if isStable(A) else "Not stable")
print("\n".join(f"{a} {b}" for a, b, c in A))

Solution (Python):
import sys
readline = 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 isStable(A):
    for i in range(0, len(A) - 1):
        if A[i][1] == A[i + 1][1]:
            if A[i][2] > A[i + 1][2]:
                return "Not stable"
    return "Stable"
n = int(input())
f = lambda a, i: (a[0], int(a[1]), i)
A = [f(readline().split(), i) for i in range(n)]
quicksort(A, 0, n - 1)
print(isStable(A))
print("\n".join(f"{a} {b}" for a, b, c in A))

Solution (Python):
def decode():
    n = int(input())
    cards = []
    for i in range(n):
        [m, v] = input().split()
        cards.append((m, int(v), i))

    return n, cards


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
            t = a[j]
            a[j] = a[i]
            a[i] = t
    t = a[i+1]
    a[i+1] = a[r]
    a[r] = t

    return i+1


def disp(cards):
    for (m, n, _) in cards:
        print("{0} {1}".format(m, n))


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


def isstable(cards):
    for i in range(len(cards) - 1):
        if cards[i][1] == cards[i+1][1]:
            if cards[i][2] < cards[i+1][2]:
                pass
            else:
                return False
    return True

if __name__ == '__main__':
    n, cards = decode()

    quicksort(cards, 0, n-1)

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

    disp(cards)

Solution (Python):
def partition(hoge, p, r):
    x = int(hoge[r][1])
    i = p-1
    for j in range(p, r):
        if int(hoge[j][1]) <= x:
            i += 1
            tmp = hoge[i]
            hoge[i] = hoge[j]
            hoge[j] = tmp
    tmp = hoge[i+1]
    hoge[i+1] = hoge[r]
    hoge[r] = tmp
    return i+1
    
def qSort(hoge, p, r):
    if p < r:
        q = partition(hoge, p, r)
        qSort(hoge, p, q-1)
        qSort(hoge, q+1, r)
    
def isStable(input_array, output_array):
    same_nums = list()
    now_num = 0
    for elem in output_array:
        if now_num != int(elem[1]):
            now_num = int(elem[1])
            same_nums = list()
        else:
            for c in same_nums:
                if input_array.index(c) > input_array.index(elem):
                    return 'Not stable'
        same_nums.append(elem)
    return 'Stable'
    
if __name__ == '__main__':
    num = int(input())
    hoge = list()
    for _ in range(num):
        c, s = input().split()
        hoge.append((c,s))
    origin = hoge[:]
    qSort(hoge, 0, len(hoge)-1)
    print(isStable(origin, hoge))
    print('\n'.join(['{0[0]} {0[1]}'.format(x) for x in hoge]))

Solution (Python):
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 m(L,R):
 T=[]
 for l in L[::-1]:
  while R and R[-1][1]>=l[1]:T+=[R.pop()]
  T+=[l]
 return R+T[::-1]
def d(A):l=len(A);s=l//2;return m(d(A[:s]),d(A[s:]))if l>1 else A
n=int(input())
f=lambda x,y:(x,int(y))
A=[f(*input().split())for _ in[0]*n]
B=A[:]
k(A,0,n-1)
print(['Not s','S'][A==d(B)]+'table')
for e in A:print(*e)

Solution (Python):
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 m(L,R):
 T=[]
 for l in L[::-1]:
  while R and R[-1][1]>=l[1]:T+=[R.pop()]
  T+=[l]
 return R+T[::-1]
def d(A):l=len(A);s=l//2;return m(d(A[:s]),d(A[s:]))if l>1 else A
n=int(input())
f=lambda x,y:(x,int(y))
A=[f(*input().split())for _ in[0]*n]
B=A[:]
k(A,0,n-1)
print(['Not s','S'][A==d(B)]+'table')
for e in A:print(*e)

Solution (Python):
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 m(L,R):
 T=[]
 for l in L[::-1]:
  while R and R[-1][1]>=l[1]:T+=[R.pop()]
  T+=[l]
 return R+T[::-1]
def d(A):l=len(A);s=l//2;return m(d(A[:s]),d(A[s:]))if l>1 else A
n=int(input())
f=lambda x,y:(x,int(y))
A=[f(*input().split())for _ in[0]*n]
B=A[:]
k(A,0,n-1)
print(['Not s','S'][A==d(B)]+'table')
for e in A:print(*e)

Solution (Python):
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 m(L,R):
 T=[]
 for l in L[::-1]:
  while R and R[-1][1]>=l[1]:T+=[R.pop()]
  T+=[l]
 return R+T[::-1]
def d(A):l=len(A);s=l//2;return m(d(A[:s]),d(A[s:]))if l>1 else A
n=int(input())
f=lambda x,y:(x,int(y))
A=[f(*input().split())for _ in[0]*n]
B=A[:]
k(A,0,n-1)
print(['Not s','S'][A==d(B)]+'table')
for e in A:print(*e)

Solution (Python):
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 m(L,R):
 T=[]
 for l in L[::-1]:
  while R and R[-1][1]>=l[1]:T+=[R.pop()]
  T+=[l]
 return R+T[::-1]
def d(A):l=len(A);s=l//2;return m(d(A[:s]),d(A[s:]))if l>1 else A
n=int(input())
f=lambda x,y:(x,int(y))
A=[f(*input().split())for _ in[0]*n]
B=A[:]
k(A,0,n-1)
print(['Not s','S'][A==d(B)]+'table')
for e in A:print(*e)

Solution (Python):
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 m(L,R):
 T=[]
 for l in L[::-1]:
  while R and R[-1][1]>=l[1]:T+=[R.pop()]
  T+=[l]
 return R+T[::-1]
def d(A):l=len(A);s=l//2;return m(d(A[:s]),d(A[s:]))if l>1 else A
n=int(input())
f=lambda x,y:(x,int(y))
A=[f(*input().split())for _ in[0]*n]
B=A[:]
k(A,0,n-1)
print(['Not s','S'][A==d(B)]+'table')
for e in A:print(*e)

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 m(L,R):
 T=[]
 for l in L[::-1]:
  while R and R[-1][1]>=l[1]:T+=[R.pop()]
  T+=[l]
 return R+T[::-1]
def d(A):l=len(A);s=l//2;return m(d(A[:s]),d(A[s:]))if l>1 else A
n=int(input())
f=lambda x,y:(x,int(y))
A=[f(*e.split())for e in sys.stdin]
B=A[:]
k(A,0,n-1)
print(['Not s','S'][A==d(B)]+'table')
for e in A:print(*e)

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 m(L,R):
 T=[]
 for l in L[::-1]:
  while R and R[-1][1]>=l[1]:T+=[R.pop()]
  T+=[l]
 return R+T[::-1]
def d(A):l=len(A);s=l//2;return m(d(A[:s]),d(A[s:]))if l>1 else A
input()
f=lambda x,y:(x,int(y))
A=[f(*e.split())for e in sys.stdin]
B=A[:]
k(A,0,len(A)-1)
print(['Not s','S'][A==d(B)]+'table')
for e in A:print(*e)