Problem:
Quick Sort Let's arrange a deck of cards. Your task is to sort totally n cards. A card consists of a part of a suit (S, H, C or D) and an number. Write a program which sorts such cards based on the following pseudocode: Partition(A, p, r)
1 x = A[r]
2 i = p-1
3 for j = p to r-1
4     do if A[j] <= x
5        then i = i+1
6            exchange A[i] and A[j] 
7 exchange A[i+1] and A[r]
8 return i+1


Quicksort(A, p, r)
1 if p < r
2    then q = Partition(A, p, r)
3        run Quicksort(A, p, q-1)
4        run Quicksort(A, q+1, r) Here, A is an array which represents a deck of cards and comparison operations are performed based on the numbers. Your program should also report the stability of the output for the given input (instance). Here, 'stability of the output' means that: cards with the same value appear in the output in the same order as they do in the input (instance). Input The first line contains an integer n , the number of cards.  n cards are given in the following lines. Each card is given in a line and represented by a pair of a character and an integer separated by a single space. Output In the first line, print the stability (" Stable " or " Not stable ") of this output. In the following lines, print the arranged cards in the same manner of that of the input. Constraints  1 ≤ n ≤ 100,000  1 ≤ the number of a card  ≤ 10 9  There are no identical card in the input  Sample Input 1 6
D 3
H 2
D 1
S 3
D 2
C 1 Sample Output 1 Not stable
D 1
C 1
D 2
H 2
D 3
S 3 Sample Input 2 2
S 1
H 1 Sample Output 2 Stable
S 1
H 1

Solution (Python):
import sys
from enum import IntEnum
from collections import defaultdict

def partition(li, p, r): 
    """Separate li with a value of li[r].
    Returns index of the partition value.

    >>> ax = [13, 19, 9, 5, 12, 8, 7, 4, 21, 2, 6, 11]
    >>> partition(ax, 0, 11)
    7
    >>> ax
    [9, 5, 8, 7, 4, 2, 6, 11, 21, 13, 19, 12]
    """
    x = li[r]
    i = p - 1 
    for j in range(p, r): 
        if li[j] <= x:
            i += 1
            li[i], li[j] = li[j], li[i]

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

    return i


def quicksort(li, p, r):
    """sort li by quick sort algorithm.

    >>> li = [3, 2, 1, 3, 2, 1]
    >>> quicksort(li, 0, 5)
    >>> li
    [1, 1, 2, 2, 3, 3]
    """
    if p < r:
        q = partition(li, p, r)
        quicksort(li, p, q-1)
        quicksort(li, q+1, r)


def is_stable(target, original):
    """Returns true if the target list is keeps
    the order of the original list.
    Assumes that the target list is sorted.

    >>> a = Card('H', 2)
    >>> b = Card('D', 2)
    >>> org = [a, b]
    >>> tg1 = [b, a]
    >>> is_stable(tg1, org)
    False
    >>> tg2 = [a, b]
    >>> is_stable(tg2, org)
    True
    """

    size = len(original)
    orgstack = defaultdict(list)
    trgstack = defaultdict(list)

    for i in range(size):
        orgstack[original[i].number].append(original[i])
        trgstack[target[i].number].append(target[i])

    for num in orgstack.keys():
        org = orgstack[num]
        trg = trgstack[num]
        if len(org) != len(trg):
            return False

        while len(org) > 0:
            if not org.pop() is trg.pop():
                return False

    return all([len(v) == 0 for k, v in trgstack.items()])


class Suit(IntEnum):
    S = 1
    H = 2
    D = 3
    C = 4


class Card:
    def __init__(self, suit, number):
        assert 1 <= number <= 10**9

        self.suit = Suit[suit]
        self.number = number

    def __eq__(self, other):
        """check object has the same value.

        >>> a = Card('H', 1)
        >>> b = Card('D', 1)
        >>> a == b
        True
        """
        return self.number == other.number

    def __gt__(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
                or self.number > other.number)

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

    def __hash__(self):
        """check object is identical.

        >>> a = Card('H', 1)
        >>> b = Card('D', 1)
        >>> a is b
        False
        """
        return hash(self.suit, self.number)

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


def run():
    count = int(input())  
    cards = []
    for line in sys.stdin:
        s, n = line.split()
        cards.append(Card(s, int(n)))

    sorted_cards = cards[:]
    quicksort(sorted_cards, 0, count-1)

    if is_stable(sorted_cards, cards):
        print('Stable')
    else:
        print('Not stable')

    for c in sorted_cards:
        print(c)


if __name__ == '__main__':
    run()

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 = i + 1
            a[i], a[j] = a[j], a[i]
    a[i + 1], a[r] = a[r], a[i + 1]
    return(i + 1)

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



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

quick_sort(a, 0, n - 1)

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

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

Solution (Python):

"""
Created on Thu May  3 21:24:25 2018
ALDS1_6_C
@author: maezawa
"""
a = []
n = int(input())
for i in range(n):
    s = input().split()
    a.append([s[0], int(s[1])])
    
a_in = a.copy()

def is_stable(a, b):
    s = True
    for i in range(n-1):
        if b[i+1][1] == b[i][1]:
            j = a.index(b[i])
            k = a.index(b[i+1])
            if j > k:
                s = False
                return s
    return s
    

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 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(a, 0, len(a)-1)
if is_stable(a_in, a):
    print('Stable')
else:
    print('Not stable')
for i in range(len(a)):
    print('{} {}'.format(a[i][0],a[i][1]))

Solution (Python):
import copy

def num_from_card(card):
    return int(card[2:])

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

def merge(A, left, mid, right):
    L = A[left: mid]
    R = A[mid: right]
    L.append('  ' + str(int(10e9 + 1)))
    R.append('  ' + str(int(10e9 + 1)))
    i, j = 0, 0
    for k in range(left, right):
        if num_from_card(L[i]) <= num_from_card(R[j]):
            A[k] = L[i]
            i += 1
        else:
            A[k] = R[j]
            j += 1

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

n = int(input())
cards = [input() for i in range(n)]
merge_cards = copy.copy(cards)

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

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

for c in cards:
    print(c)

Solution (Python):




import sys

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

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

    return i+1

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

def check_stable(A):
    prev_val = None
    for card in A:
        if card.val == prev_val:
            if card.pos < prev_pos:
                print('Not stable')
                return
        prev_val = card.val
        prev_pos = card.pos

    print('Stable')
    return


n = int(sys.stdin.readline())
A = list()
for pos in range(n):
    suit, val_s = sys.stdin.readline().split()
    A.append(Card(suit, int(val_s), pos))

quicksort(A, 0, n-1)
check_stable(A)
for card in A:
    print(card.suit, card.val)

Solution (Python):
class Num:
    a=0
    b=0
    origin=0

def partition(A, p, r):
    x=A[r].b
    i=p-1
    for j in range(p,r):
        if A[j].b <= x:
            i += 1
            A[i].b,A[j].b = A[j].b,A[i].b
            A[i].a,A[j].a = A[j].a,A[i].a
            A[i].origin,A[j].origin = A[j].origin,A[i].origin
    A[i+1].b,A[r].b = A[r].b,A[i+1].b
    A[i+1].a,A[r].a = A[r].a,A[i+1].a
    A[i+1].origin,A[r].origin = A[r].origin,A[i+1].origin
    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 isStable(A):
    flag=True
    n=len(A)
    for i in range(n-1):
        if A[i].b == A[i+1].b and A[i].origin > A[i+1].origin:
            flag = False
    return flag

if __name__ == "__main__":
    
    n=int(input())
    A=[]
    for i in range(n):
        num =Num()
        a=input().split()
        num.a = a[0]
        num.b = int(a[1])
        num.origin=i
        A.append(num)
    quick_sort(A,0,n-1)
    if isStable(A):
        print("Stable")
    else:
        print("Not stable")
    for i in A:
        print(i.a,end=" ")
        print(i.b)

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

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

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

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


quick_sort(trump,0,n)
if(isStable(trump)):
    print('Stable')
else:
    print('Not stable')
for i in trump:
    print('{} {}'.format(i[0], i[1]))

Solution (Python):
INF = 10**10


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

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

    return i + 1


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


def merge(ary, left, mid, right):
    lry = ary[left:mid]
    rry = ary[mid:right]
    lry.append(('INF', INF))
    rry.append(('INF', INF))

    i = 0
    j = 0
    for k in range(left, right):
        if lry[i][1] <= rry[j][1]:
            ary[k] = lry[i]
            i += 1
        else:
            ary[k] = rry[j]
            j += 1

    return right - left


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

    return cnt



import sys
from copy import deepcopy

n = int(input())


ary = [(lambda x: (x[0], int(x[1])))(line.strip().split()) for line in sys.stdin]

qary = deepcopy(ary)
mary = deepcopy(ary)
quick_sort(qary, 0, n - 1)
merge_sort(mary, 0, n)

if qary == mary:
    print('Stable')
else:
    print('Not stable')
[print(*_) for _ in qary]

Solution (Python):
INF = 10**10


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

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

    return i + 1


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


def merge(ary, left, mid, right):
    lry = ary[left:mid]
    rry = ary[mid:right]
    lry.append(('INF', INF))
    rry.append(('INF', INF))

    i = 0
    j = 0
    for k in range(left, right):
        if lry[i][1] <= rry[j][1]:
            ary[k] = lry[i]
            i += 1
        else:
            ary[k] = rry[j]
            j += 1

    return right - left


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

    return cnt


if __name__ == '__main__':
    import sys
    from copy import deepcopy

    n = int(input())
    ary = [(lambda x: (x[0], int(x[1])))(line.strip().split()) for line in sys.stdin]

    qary = deepcopy(ary)
    mary = deepcopy(ary)
    quick_sort(qary, 0, n - 1)
    merge_sort(mary, 0, n)

    if qary == mary:
        print('Stable')
    else:
        print('Not stable')
    [print(*_) for _ in qary]

Solution (Python):
INF = 10**10


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

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

    return i + 1


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


def merge(ary, left, mid, right):
    lry = ary[left:mid]
    rry = ary[mid:right]
    lry.append(('INF', INF))
    rry.append(('INF', INF))

    i = 0
    j = 0
    for k in range(left, right):
        if lry[i][1] <= rry[j][1]:
            ary[k] = lry[i]
            i += 1
        else:
            ary[k] = rry[j]
            j += 1

    return right - left


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

    return cnt


if __name__ == '__main__':
    import sys
    from copy import deepcopy

    n = int(input())
    
    ary = [(lambda x: (x[0], int(x[1])))(input().split()) for i in range(n)]

    qary = deepcopy(ary)
    mary = deepcopy(ary)
    quick_sort(qary, 0, n - 1)
    merge_sort(mary, 0, n)

    if qary == mary:
        print('Stable')
    else:
        print('Not stable')
    [print(*_) for _ in qary]

Solution (Python):
INF = 10**10


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

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

    return i + 1


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


def merge(ary, left, mid, right):
    lry = ary[left:mid]
    rry = ary[mid:right]
    lry.append(('INF', INF))
    rry.append(('INF', INF))

    i = 0
    j = 0
    for k in range(left, right):
        if lry[i][1] <= rry[j][1]:
            ary[k] = lry[i]
            i += 1
        else:
            ary[k] = rry[j]
            j += 1

    return right - left


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

    return cnt


if __name__ == '__main__':
    import sys
    from copy import deepcopy

    n = int(input())
    
    ary = [(lambda x: (x[0], int(x[1])))(input().split()) for i in range(n)]

    qary = deepcopy(ary)
    mary = deepcopy(ary)
    quick_sort(qary, 0, n - 1)
    merge_sort(mary, 0, n)

    if qary == mary:
        print('Stable')
    else:
        print('Not stable')
    [print(*_) for _ in qary]

Solution (Python):
def merge(A, left, mid, right):
    n1 = mid - left
    n2 = right - mid
    L, R = A[left: left + n1], A[mid: mid + n2]

    L.append([0,2000000000])
    R.append([0,2000000000])

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


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


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 = []
merge_cards = []
for _ in range(n):
    tmp = input().split(' ')
    cards.append([tmp[0], int(tmp[1])])
    merge_cards.append([tmp[0], int(tmp[1])])

mergeSort(merge_cards, 0, n)

quick_sort(cards, 0, n - 1)

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

for card in cards:
    print(*card)

Solution (Python):
def partition(num_list, start, end):
    split = start -1
    x = int(num_list[end][1])
    for i in range(start, end):
        if int(num_list[i][1]) <= x:
            split += 1
            num_list[split], num_list[i] = num_list[i], num_list[split]
    num_list[split+1], num_list[end] = num_list[end], num_list[split+1]
    return split+1

def quickSort(num_list, start, end):
    if start < end:
        q = partition(num_list, start, end)
        quickSort(num_list, start, q-1)
        quickSort(num_list, q+1, end)

import sys, copy
n = int(input())
input_list = [sys.stdin.readline().rstrip().split() for i in range(n)]
check_list = copy.deepcopy(input_list)
quickSort(input_list, 0, n-1)
for i in range(n-1):
    if input_list[i][1] == input_list[i+1][1]:
        if check_list.index(input_list[i]) > check_list.index(input_list[i+1]):
            print('Not stable')
            break
else:
    print('Stable')
for i in input_list:
    print('{} {}'.format(i[0], i[1]))

Solution (Python):

from copy import deepcopy
n = int(input())
A = []
for i in range(n):
    ch, num = input().split()
    A.append([ch, int(num)])

B = deepcopy(A)



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

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

    

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


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




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

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

Solution (Python):
def partition(a, p, r):
    x = a[r]["value"]
    i = p - 1
    for j in range(p, r):
        if a[j]["value"] <= x:
            i += 1
            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 print_a(a):
    for x in a:
        print(x["design"], x["value"])


n = int(input())
a = []
for _ in range(n):
    s = input().split()
    a.append({"design": s[0], "value": int(s[1])})
b = a.copy()

quick_sort(a, 0, n - 1)

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

print_a(a)

Solution (Python):
def quicksort(A, p, r):
    if p < r:
        q = patation(A, p, r)
        quicksort(A, p, q-1)
        quicksort(A, q+1, r)

def patation(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
            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 print_list(A):
    if A == B:
        print("Stable")
    else:
        print("Not stable")

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

A = []
n = int(input())
for i in range(n):
    A.append(input().split())
B = sorted(A, key=lambda x: x[1])
p = 0; r = n - 1
quicksort(A, p, r)
print_list(A)

Solution (Python):
def partition(a, p, r):
    q = p
    for i in range(p, r):
        if a[i][1] <= a[r][1]:
            a[q], a[i] = a[i], a[q]
            q += 1
    a[q], a[r] = a[r], a[q]
    return q 
   
def quicksort(a, p, r):
    if p < r:
        q = partition(a, p, r)
        quicksort(a, p, q-1)
        quicksort(a, q+1, r)
   
def check_stable(a):
    for i in range(1, len(a)):
        if a[i - 1][1] == a[i][1]:
            if a[i - 1][2] > a[i][2]:
                return 'Not stable'
    return 'Stable'
       
import sys
n = int(sys.stdin.readline())
a = []
for i in range(n):
    suit, num = sys.stdin.readline().split()
    a += [[suit, int(num), i]]
   
quicksort(a, 0, len(a) - 1)
print(check_stable(a))
   
for line in a:
    print(line[0],line[1])

Solution (Python):
def main() :
    n = int(input())
    cards = [Card(*input().split()) for i in range(n)]
    stableCards = sorted(cards[:], key=lambda c: c.number)
    quickSort(cards, 0, n - 1)
    print(isStable(cards, stableCards, n))
    list(map(lambda i : i.print_card(), cards))

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

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

def isStable(a, b, n):
    for i in range(n):
        if a[i].prefix != b[i].prefix:
            return 'Not stable'

    return 'Stable'

class Card():
    def __init__(self, prefix, number):
        self.prefix = prefix
        self.number = number

    def print_card(self):
        print(self.prefix, self.number)

if __name__ == '__main__':
    main()

Solution (Python):
def main() :
    n = int(input())
    cards = [Card(*input().split()) for i in range(n)]
    stableCards = sorted(cards[:], key=lambda c: c.number)
    quickSort(cards, 0, n - 1)
    print(isStable(cards, stableCards, n))
    list(map(lambda i : i.print_card(), cards))

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

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

def isStable(a, b, n):
    for i in range(n):
        if a[i].prefix != b[i].prefix:
            return 'Not stable'

    return 'Stable'

class Card():
    def __init__(self, prefix, number):
        self.prefix = prefix
        self.number = number

    def print_card(self):
        print(self.prefix, self.number)

if __name__ == '__main__':
    main()

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

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

def order(A):
    return sorted(A, key = lambda e: e[0])

n = int(input())
x = [[] for i in range(n)]
for i in range(n):
    a, b = raw_input().split()
    x[i] = (int(b), 'SHDC'.index(a))

x1 = x + []
quicksort(x1, 0, n-1)

if x1 == order(x):
    print 'Stable'
else:
    print 'Not stable'
for e in x1:
    print 'SHDC'[e[1]], e[0]

Solution (Python):

from __future__ import division, print_function
from sys import stdin


def patition(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_sort(a, p, r):
    if p < r:
        q = patition(a, p, r)
        quick_sort(a, p, q-1)
        quick_sort(a, q+1, r)


n = int(stdin.readline())
data = []
s = set()
for i in range(n):
    c, num = stdin.readline().split()
    data.append((int(num), c))
    s.add(int(num))
output = data[:]
quick_sort(output, 0, n-1)
for i in s:
    if [d for d in data if d[0] == i] != [d for d in output if d[0] == i]:
        print('Not stable')
        break
else:
    print('Stable')
for num, c in output:
    print(c, num)

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


def merge(A, left, mid, right):
    L = A[left:mid] + [[10000000000, 'S']]
    R = A[mid:right] + [[10000000000, 'S']]

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

n = int(input())
lstA = []
for i in range(n):
    C, N = input().split()
    k = [int(N), C]
    lstA.append(k)

lstB = copy.copy(lstA)
mergeSort(lstA, 0, n)
quicksort(lstB, 0, n-1)

if lstA == lstB:
    print('Stable')

else:
    print('Not stable')

for i in lstB:
    print(i[1], i[0])

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

def Merge(As, Ms, l, m, r):
    global cnt
    cnt += r - l
    L = As[l:m] + [float('inf')]
    R = As[m:r] + [float('inf')]
    Lm = Ms[l:m]
    Rm = Ms[m:r]
    i, j = 0, 0
    for k in range(l, r):
        if L[i] <= R[j]:
            As[k] = L[i]
            Ms[k] = Lm[i]
            i += 1
        else:
            As[k] = R[j]
            Ms[k] = Rm[j]
            j += 1
    return

def MergeSort(As, Ms, l, r):
    if r - l > 1:
        m = (l + r) // 2
        MergeSort(As, Ms, l, m)
        MergeSort(As, Ms, m, r)
        Merge(As, Ms, l, m, r)
    return

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

def QuickSort(A, p, r):
    if p < r:
        m = Partition(A, p, r)
        QuickSort(A, p, m-1)
        QuickSort(A, m+1, r)

n = int(input())
M, A = [], []
for i in range(n):
    a, b = input().split()
    M.append(a)
    A.append(int(b))
As = A[:]
Ms = M[:]
QuickSort(A, 0, n-1)
MergeSort(As, Ms, 0, n)
if M == Ms:
    print('Stable')
else:
    print('Not stable')
for i in range(n):
    print('{} {}'.format(M[i], A[i]))

Solution (Python):
def make_card(i, card):
    suit, value = card.split()
    return (int(value), i, card)


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


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


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


n = int(input())
a = list(make_card(i, input()) for i in range(n))
b = a[:]

quick_sort(a, 0, n - 1, partition_not_stable)
quick_sort(b, 0, n - 1, partition_stable)
print(('S' if a == b else 'Not s') + 'table')
print('\n'.join(card[2] for card in a))

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

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

def stable(A,Q):
    for i in range(1,len(Q)):
        if int(Q[i-1][1]) == int(Q[i][1]):
            x = A.index(Q[i-1])
            y = A.index(Q[i])
            if y<x:
                return 'Not stable'
    return 'Stable'

n = int(input())
A = []
for i in range(n):
    a = input().split()
    a[1]=int(a[1])
    A.append(a)
Q = A.copy()
quicksort(Q, 0, n-1)
print(stable(A,Q))
for i in range(len(Q)):
    print(Q[i][0], Q[i][1])

Solution (Python):
def partition(a, p, r):
    """パーティション分割"""
    x = int(a[r].split()[1])
    i = p - 1
    for j in range(p, r):
        if int(a[j].split()[1]) <= x:
            i = i + 1
            a[i], a[j] = a[j], a[i]
    a[i+1], a[r] = a[r], a[i+1]
    return i + 1


def quick_sort(a, p, r):
    if p < r:
        
        q = partition(a, p, r)

        
        quick_sort(a, p, q-1)
        quick_sort(a, q+1, r)


n = int(input())
li = [input().splitlines()[0] for x in range(n)]
stable = sorted(li, key=lambda x: int(x.split()[1]))



quick_sort(li, 0, n - 1)

print("S" if stable == li else "Not s", end="")
print("table")
for i in li:
    print(i)