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):
n = int(raw_input())


class Card():
    __slots__ = ('suit', 'value')


A = [Card() for _ in xrange(n)]

B = [Card() for _ in xrange(n)]

s = set()
for i in xrange(n):
    a = raw_input().split()
    A[i].suit = a[0]
    B[i].suit = a[0]
    A[i].value = int(a[1])
    B[i].value = int(a[1])
    s.add(int(a[1]))

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

quickSort(B, 0, n-1)

for i in s:
    if [d.suit for d in A if d.value == i] != [d.suit for d in B if d.value == i]:
        print('Not stable')
        break
else:
    print('Stable')

for i in xrange(n):
    print B[i].suit, B[i].value

Solution (Python):
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 is_stable(cards):
    for i in range(1, len(cards)):
        if cards[i-1][1] == cards[i][1]:
            if cards[i-1][2] > cards[i][2]:
                return False
    return True


n = int(input())
cards = []
for i in range(n):
    cards.append(input().split() + [i])
quicksort(cards, 0, n - 1)
print("Stable" if is_stable(cards) else "Not stable")
for card in cards:
    print(card[0], card[1])

Solution (Python):
def partition(A,p,r):
    x=A[r][1]
    i=p-1
    for j in xrange(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 merge(A,left,mid,right):
    n1=mid-left
    n2=right-mid
    l=[A[left+i] for i in xrange(n1)]
    r=[A[mid+i] for i in xrange(n2)]
    l.append([0,float('inf')])
    r.append([0,float('inf')])
    i=0
    j=0
    for k in xrange(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=input()
card_1=[[0]*2 for i in xrange(n)]

for i in xrange(n):
    card_1[i][0],card_1[i][1]=map(str,raw_input().split())
    card_1[i][1]=int(card_1[i][1])

card_2=list(card_1)
quicksort(card_1,0,n-1)
mergesort(card_2,0,n)

if card_1==card_2:
    print("Stable")
else :
    print("Not stable")

for i in xrange(n):
    card_1[i]=map(str,card_1[i])
    print(" ".join(card_1[i]))

Solution (Python):
import sys

class card:
    def __init__(self, types, value):
        self.types = types
        self.value = value

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

    return i + 1

def swap(array, i, j):
    tmp = array[i]
    array[i] = array[j]
    array[j] = tmp

def checkStable(origin, sorted, N):
    for i in range(0, N - 1):
        if sorted[i].value == sorted[i + 1].value:
            if origin.index(sorted[i]) > origin.index(sorted[i + 1]):
                return False
    return True

if __name__ == "__main__":
    lines = sys.stdin.readlines()
    del lines[0]
    A = [card(c[0], int(c[2:])) for c in lines]
    origin = A[:]
    quickSort(A, 0, len(A) - 1)
    if checkStable(origin, A, len(A)):
        print "Stable"
    else:
        print "Not stable"
    for a in A:
        print a.types + " " + str(a.value)

Solution (Python):
import sys

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

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 = 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 checkStable(origin, sorted):
    for i in range(0, len(origin) - 1):
        if sorted[i].num == sorted[i + 1].num:
            if origin.index(sorted[i]) > origin.index(sorted[i + 1]):
                return False
    return True

if __name__ == "__main__":
    lines = sys.stdin.readlines()
    del lines[0]
    A = [card(c[0], int(c[2:])) for c in lines]
    origin = A[:]
    quickSort(A, 0, len(A) - 1)

    if checkStable(origin, A):
        print "Stable"
    else:
        print "Not stable"

    for a in A:
        print a.suit, str(a.num)

Solution (Python):


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

def 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())
data = []
s = set()
for i in range(n):
    c, num = map(str, raw_input().split())
    data.append((int(num), c))
    s.add(int(num))
out = data[:]
quick_sort(out, 0, n-1)
for i in s:
    if [d for d in data if d[0] == i] != [d for d in out if d[0] == i]:
        print "Not stable"
        break
else:
    print "Stable"
for num, c in out:
    print "%s %s" %(c, num)

Solution (Python):
from collections import namedtuple
Card = namedtuple('Card', 'suit value')

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

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

def merge(L,R):
    global cnt
    n = len(L)+len(R)
    A = []
    i = j = 0
    L.append(Card('X',-1))
    R.append(Card('X',-1))
    for _ in range(n):
        if L[i].value > R[j].value:
            A.append(L[i])
            i += 1
        else:
            A.append(R[j])
            j += 1
    return A

def mergeSort(A):
    if len(A)==1: return A
    m = len(A)//2
    return merge(mergeSort(A[:m]),mergeSort(A[m:])) 

if __name__=='__main__':
    n = int(input()) 
    Co = list(map(lambda X: Card(X[0],int(X[1])), [input().split() for _ in range(n)]))
    Cq = Co[:]
    Cm = mergeSort(Co[:])
    quickSort(Cq,0,n-1)
    print("Stable" if Cq==Cm[::-1] else "Not stable")
    for c in Cq: print(c.suit,c.value)

Solution (Python):
from collections import namedtuple
Card = namedtuple('Card', 'suit value')

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

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

def isStable(Co,Cs):
    C = Cs[:]
    for ci in Co:
        j = C.index(ci)
        if j > 0:
            if Cs[j-1].value == ci.value:
                return False
        del C[j]
    return True

if __name__=='__main__':
    n = int(input()) 
    Co = list(map(lambda X: Card(X[0],int(X[1])), [input().split() for _ in range(n)]))
    Cs = Co[:]
    quickSort(Cs,0,n-1)
    print("Stable" if isStable(Co,Cs) else "Not stable")
    for c in Cs: print(c.suit,c.value)

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

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

    a[i+1], a[r] = a[r], a[i+1]
    return i+1


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


def isstable(a):
    for i in range(n-1):
        if a[i][1] == a[i+1][1]:
            if a[i][2] > a[i+1][2]:
                return False
    return True


n = int(input())
deck = [None]*n
for num in range(n):
    card = input().split()
    deck[num] = [card[0], int(card[1]), num]

quicksort(deck, 0, n-1)
if isstable(deck):
    print("Stable")
else:
    print("Not stable")
[print(deck[i][0], deck[i][1]) for i in range(n)]

Solution (Python):
import sys
import copy

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 += 1
            tmp = A[i]
            A[i] = A[j]
            A[j] = tmp

    tmp = A[i+1]
    A[i+1] = A[r-1]
    A[r-1] = tmp
    return i+1

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

def babble_sort(A, n):
    for j in range(n):
        for i in range(n-1):
            if A[i+1][1] < A[i][1]:
                tmp = A[i+1]
                A[i+1] = A[i]
                A[i] = tmp
    return A

def stable(A, B):
    for i in range(0, len(A)):
        if A[i][0] != B[i][0]:
            return False
    return True


n = int(sys.stdin.readline())

A = [[x[0], int(x[1])] for x in [y.split() for y in sys.stdin.read().split("\n")[:-1]]]

B = sorted(copy.deepcopy(A), key=lambda x: x[1])
C = quicksort(copy.deepcopy(A), 0, n)

if stable(C, B):
    print('Stable')
else:
    print("Not stable")

for i in C:
    print(*i)

Solution (Python):


def partition(target_list, l, r):
    x = int(target_list[r][1:])
    i = l - 1

    for j in range(l, r):
        if int(target_list[j][1:]) <= x:
            i = i + 1
            tmp = target_list[i]
            target_list[i] = target_list[j]
            target_list[j] = tmp
    tmp = target_list[r]
    target_list[r] = target_list[i + 1]
    target_list[i + 1] = tmp
    
    return  i + 1

def merge(l,r):
    
    l_index = 0
    r_index = 0
    merge_list = []
    l.append("X " + str(pow(10,9) + 1))
    r.append("X " + str(pow(10,9) + 1))
   
    for k in range(len(l) + len(r) - 2):
        if int(l[l_index][1:]) <= int(r[r_index][1:]):
            merge_list.append(l[l_index])
            l_index += 1
        else:
            merge_list.append(r[r_index])
            r_index += 1
    
    return merge_list
    
def merge_sort(target_list):
    if len(target_list) == 1:
        return target_list
    
    mid = int(len(target_list) / 2)
    l = merge_sort(target_list[:mid])
    r = merge_sort(target_list[mid:])
    
    return merge(l, r)

def check_stable(origin_list, target_list):
    sorted_list = merge_sort(origin_list)
    if sorted_list == target_list:
        return "Stable"
    return "Not stable"

def quick_sort(target_list, l, r):
    if l < r:
        c = partition(target_list, l, r)
        quick_sort(target_list, l, c - 1)
        quick_sort(target_list, c + 1, r)
        
if __name__ == "__main__":
    n_list = int(input())

    target_list = []
    for i in range(n_list):
        target_list.append(input())
    origin_list = [a for a in target_list]
    quick_sort(target_list, 0, n_list - 1)
    print(check_stable(origin_list, target_list))
    print("\n".join(target_list))

Solution (Python):




import sys
import copy


def partition(array, start, end):
    x = int(array[end][2:])
    i = start - 1
    assert start <= end
    for j in range(start, end):
        if int(array[j][2:]) <= x:
            i += 1
            array[i], array[j] = array[j], array[i]
    array[i + 1], array[end] = array[end], array[i + 1]
    return i + 1


def quick_sort(array, start, end):
    if start < end:
        cursor = partition(array, start, end)
        quick_sort(array, start, cursor - 1)
        quick_sort(array, cursor + 1, end)
    return array


def merge(A, left, mid, right):
    L = A[left:mid] + ['N ' + str(int(1e9 + 1))]
    R = A[mid:right] + ['N ' + str(int(1e9 + 1))]

    i, j = 0, 0

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

    return None


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


if __name__ == '__main__':
    _input = sys.stdin.readlines()
    array_length = int(_input[0])
    array = list(map(lambda x: x.strip('\n'), _input[1:]))
    assert len(array) == array_length

    merge_array = copy.deepcopy(array)

    
    merge_result = merge_sort(A=merge_array, left=0, right=array_length)
    

    
    quick_result = quick_sort(array=array, start=0, end=array_length - 1)
    if quick_result != merge_result:
        print('Not stable')
    else:
        print('Stable')
    print(*quick_result, sep='\n')

Solution (Python):



"""
Input:
6
D 3
H 2
D 1
S 3
D 2
C 1

Output:
Not stable / Stable
D 1
C 1
D 2
H 2
D 3
S 3
"""
import sys
import copy


def partition(array, start, end):
    x = int(array[end][2:])
    i = start - 1
    assert start <= end
    for j in range(start, end):
        if int(array[j][2:]) <= x:
            i += 1
            array[i], array[j] = array[j], array[i]
    array[i + 1], array[end] = array[end], array[i + 1]
    return i + 1


def quick_sort(array, start, end):
    if start < end:
        cursor = partition(array, start, end)
        quick_sort(array, start, cursor - 1)
        quick_sort(array, cursor + 1, end)
    return array


def merge(A, left, mid, right):
    L = A[left:mid] + ['N ' + str(int(1e9 + 1))]
    R = A[mid:right] + ['N ' + str(int(1e9 + 1))]

    i, j = 0, 0

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

    return None


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


if __name__ == '__main__':
    _input = sys.stdin.readlines()
    array_length = int(_input[0])
    array = list(map(lambda x: x.strip('\n'), _input[1:]))
    assert len(array) == array_length

    merge_array = copy.deepcopy(array)

    
    merge_result = merge_sort(A=merge_array, left=0, right=array_length)
    

    
    quick_result = quick_sort(array=array, start=0, end=array_length - 1)
    if quick_result != merge_result:
        print('Not stable')
    else:
        print('Stable')
    print(*quick_result, sep='\n')

Solution (Python):



"""
Input:
6
D 3
H 2
D 1
S 3
D 2
C 1

Output:
Not stable / Stable
D 1
C 1
D 2
H 2
D 3
S 3
"""
import sys
import copy


def partition(_array, start, end):
    x = int(_array[end][2:])
    i = start - 1
    assert start <= end
    for j in range(start, end):
        if int(_array[j][2:]) <= x:
            i += 1
            _array[i], _array[j] = _array[j], _array[i]
    _array[i + 1], _array[end] = _array[end], _array[i + 1]
    return i + 1


def quick_sort(_array, start, end):
    if start < end:
        cursor = partition(_array, start, end)
        quick_sort(_array, start, cursor - 1)
        quick_sort(_array, cursor + 1, end)
    return _array


def merge(_array, left, mid, right):
    array_left = _array[left:mid] + ['N ' + str(int(1e9 + 1))]
    array_right = _array[mid:right] + ['N ' + str(int(1e9 + 1))]

    i, j = 0, 0

    for k in range(left, right):
        if int(array_left[i][2:]) <= int(array_right[j][2:]):
            _array[k] = array_left[i]
            i += 1
        else:
            _array[k] = array_right[j]
            j += 1

    return None


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


if __name__ == '__main__':
    _input = sys.stdin.readlines()
    array_length = int(_input[0])
    array = list(map(lambda x: x.strip(), _input[1:]))
    

    merge_array = copy.deepcopy(array)
    merge_result = merge_sort(_array=merge_array, left=0, right=array_length)
    
    quick_result = quick_sort(_array=array, start=0, end=array_length - 1)

    if quick_result != merge_result:
        print('Not stable')
    else:
        print('Stable')
    print(*quick_result, sep='\n')

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 checker(A,start,end):
    for i in range(start,end-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())
l = []
for i in range(n):
    card = input().split()
    l.append((card[0],int(card[1]),i))
quickSort(l,0,n-1)
print(checker(l,0,n))
for s,n,c in l:
    print("{} {}".format(s,n))

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


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


def partition(A, p, r):
    """
    ???????????????????????????????????????A[r]?????°?????????????????????????????????????????????A[r-1]??¨?´??????????????????§??¨???
    """
    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)


if __name__ == '__main__':
    
    
    
    num_of_cards = int(input())
    cards = []
    for i in range(num_of_cards):
        suit, rank = input().split(' ')
        cards.append((suit, int(rank)))
    comp_cards = cards[:]


    
    data_length = len(cards)
    quick_sort(cards, 0, data_length-1)
    merge_sort(comp_cards, 0, data_length)  

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

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

Solution (Python):






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

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


def stable_check(sorted_values,sorted_suits,default_values,default_suits,n):
    for i in set(sorted_values):
        check_ss = []
        check_ds = []
        if i in sorted_values:
            for x in xrange(n):
                if i == sorted_values[x]:
                    check_ss.append(sorted_suits[x])
                if i == default_values[x]:
                    check_ds.append(default_suits[x])
            for x in xrange(len(check_ss)):
                if check_ss[x]!=check_ds[x]:
                    return "Not stable"
    return "Stable"

def main():
    n = input()
    A = []
    B = []
    for i in xrange(n):
        b,a = raw_input().split()
        A.append(int(a))
        B.append(b)
    cpA=list(A)
    setA = set(A)
    cpB=list(B)
    quick_sort(A,B,0,n-1)

    
    print stable_check(A,B,cpA,cpB,n)
    for i in xrange(n):
        line = "%s %s"%(B[i],A[i])
        print line

if __name__ == '__main__':
    main()

Solution (Python):
import sys

class Card:
    def __init__(self, s, n, i):
        self.suit = s
        self.num = n
        self.ini_ord = i

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

    return True

def partition(A, p, r):
    x = A[r].num
    i = p - 1

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

    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(sys.stdin.readline().rstrip())
cards = []

for i in range(n):
    line = sys.stdin.readline().split()
    cards.append(Card(line[0], int(line[1]), i))

quickSort(cards, 0, n - 1)

if is_stable(cards, n):
    print("Stable")
else:
    print("Not stable")

for i in range(n):
    print(cards[i].suit,str(cards[i].num))

Solution (Python):
def is_stable(before_sort, after_sort):
    current_num = 0
    same_number_card = list()
    for num in after_sort:
        if current_num == int(num[1]):
            for same_card in same_number_card:
                if before_sort.index(same_card) > before_sort.index(num):
                    return False
            same_number_card.append(num)
        else:
            current_num = int(num[1])
            same_number_card = [num,]
    return True

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)

if __name__ == '__main__':
    n = int(input())
    cards = list()
    for i in range(n):
        card = input().split()
        card[1] = int(card[1])
        cards.append(card)
    before_cards = list(cards)
    quicksort(cards, 0, n-1)
    print('Stable') if is_stable(before_cards, cards) else print('Not stable')
    for card in cards:
        print(*card)

Solution (Python):
def mergesort(A, s, e):
    if s + 1 < e:
        m = (e + s) // 2
        mergesort(A, s, m)
        mergesort(A, m, e)
        merge(A, s, m, e)


def merge(A, s, m, e):
    L = A[s:m] + [('*', 1E10)]
    R = A[m:e] + [('*', 1E10)]
    ix_l = ix_r = 0
    for ix in range(s, e):
        if L[ix_l][1] <= R[ix_r][1]:
            A[ix] = L[ix_l]
            ix_l += 1
        else:
            A[ix] = R[ix_r]
            ix_r += 1


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:
        i = partition(A, p, r)
        quicksort(A, p, i - 1)
        quicksort(A, i + 1, r)


if __name__ == '__main__':
    N = int(input().strip())
    AA = [0] * N
    for i in range(N):
        key, val = input().strip().split()
        val = int(val)
        AA[i] = (key, val)
    AA2 = AA[:]
    quicksort(AA, 0, len(AA) - 1)
    mergesort(AA2, 0, len(AA2))
    if all([a == a2 for a, a2 in zip(AA, AA2)]):
        print('Stable')
    else:
        print('Not stable')
    for key, val in AA:
        print('{} {}'.format(key, val))

Solution (Python):

def partition(a,b,c,p,r):
  x = a[r]
  i = p - 1
  
  for j in range(p,r):
    if x >= a[j]:
      i += 1
      a[i],a[j] = a[j],a[i]
      b[i],b[j] = b[j],b[i]
      c[i],c[j] = c[j],c[i]
      
  a[i+1],a[r] = a[r],a[i+1]
  b[i+1],b[r] = b[r],b[i+1]  
  c[i+1],c[r] = c[r],c[i+1]
  return i+1
  
def quickSort(a,b,c,p,r):
  if p < r:
    q = partition(a,b,c,p,r)
    quickSort(a,b,c,p,q-1)
    quickSort(a,b,c,q+1,r)
  
def checkStable(a,b):
  for i in range(1,len(a)):
    if a[i-1] == a[i]:
      if b[i-1] > b[i]:
        return "Not stable"
  return "Stable"
  
n = int(input())
mark = [""]*n
num = [0]*n
count = [i for i in range(n)]
for i in range(n):
  mark[i],num[i] = input().split()
num = list(map(int,num))

quickSort(num,mark,count,0,n-1)
print(checkStable(num,count))
for i in range(n):
  print(mark[i],num[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 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 is_stable(A, B):
  ma = {}
  for suit, num in A:
    if num not in ma: ma[num] = []
    ma[num].append(suit)

  mb = {}
  for suit, num in B:
    if num not in mb: mb[num] = []
    mb[num].append(suit)

  for num in ma:
    if ma[num] != mb[num]: return False

  return True

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

B = A[:]
quick_sort(A, 0, len(A) - 1)
print("Stable" if is_stable(A, B) else "Not stable")
for suit, num in A: print("{} {}".format(suit, num))

Solution (Python):
from collections import namedtuple

Card = namedtuple('Card', ['suit', 'value', 'init'])

def QuickSort(A, begin, end):
    if end - begin <= 1:
        return

    piv = A[end - 1].value
    left, right = begin, begin

    for i in range(begin, end - 1):
        if A[i].value <= piv:
            if i - left > 0:
                A[left], A[i] = A[i], A[left]
            left += 1

    A[left], A[end - 1] = A[end - 1], A[left]

    QuickSort(A, begin, left)
    QuickSort(A, left + 1, end)

n = int(input())

A = []

for i in range(n):
    suit, value = input().split()
    value = int(value)
    A.append(Card(suit, value, i))

QuickSort(A, 0, n)

for i in range(n - 1):
    if A[i].value == A[i + 1].value and A[i].init > A[i + 1].init:
        print('Not stable')
        break
else:
    print('Stable')

for a in A:
    print(a.suit, a.value)

Solution (Python):
from sys import stdin
from collections import namedtuple

Card = namedtuple('Card', ['suit', 'value', 'init'])

def QuickSort(A, begin, end):
    if end - begin <= 1:
        return

    piv = A[end - 1].value
    left, right = begin, begin

    for i in range(begin, end - 1):
        if A[i].value <= piv:
            if i - left > 0:
                A[left], A[i] = A[i], A[left]
            left += 1

    A[left], A[end - 1] = A[end - 1], A[left]

    QuickSort(A, begin, left)
    QuickSort(A, left + 1, end)

n = int(stdin.readline())
A = [None] * n

for i in range(n):
    suit, value = stdin.readline().split()
    A[i] = Card(suit, int(value), i)

QuickSort(A, 0, n)

for i in range(n - 1):
    if A[i].value == A[i + 1].value and A[i].init > A[i + 1].init:
        print('Not stable')
        break
else:
    print('Stable')

for a in A:
    print(a.suit, a.value)

Solution (Python):
def partition(A, p, r):
 x = A[r]
 i  = p-1
 for j in range(p,r):
  if int(A[j][1]) <= int(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):
    L = A[left:mid] + [[0,1000000001]]
    R = A[mid:right] + [[0,1000000001]]
    i = j = 0
    for k in range(left, right):
        if int(L[i][1]) <= int(R[j][1]):
            A[k] = L[i]
            i += 1
        else:
            A[k] = R[j]
            j += 1
 
def mergeSort(A, left, right):
    if left + 1 < right:
        mid = (left + right) // 2
        mergeSort(A, left, mid)
        mergeSort(A, mid, right)
        merge(A, left, mid, right)


n = int(input())
A = [input().split() for i in range(n)]
B = A[:]
quicksort(A, 0, n-1)
mergeSort(B, 0, n)

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

for i in range(n):
 print(" ".join(A[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 = 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 check(A, s, e):
   for i in range(s,e-1):
      if A[i][1] == A[i+1][1]:
         if A[i][2] > A[i+1][2]:
            return "Not stable"
   return "Stable"

r = int(input())
a = []
for i in range(r):
   c = input().split()
   a.append((c[0],int(c[1]),i))
quickSort(a, 0, r-1)
print(check(a,0,r))
for s,r,d in a:
   print("{} {}".format(s,r))

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:
            A[i+1], A[j] = A[j], A[i+1]
            i += 1
    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 is_stable(A):
    for i in range(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())
cards = []
for i in range(n):
    suit, num = input().split()
    cards.append([suit, int(num), i])

quick_sort(cards, 0, n-1)

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

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