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


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

Solution (Python):
def partition(A, p, r):
    x = A[r][1]
    i = p - 2
    for j in range(p-1, r):
        if A[j][1] <= x:
            i = i + 1
            hoge = A[i]
            A[i] = A[j]
            A[j] = hoge
    hoge = A[i+1]
    A[i+1] = A[r]
    A[r] = hoge
    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)
        
    return

def isStable(inData, outData, N):
    for i in range(N):
        if inData[i][0] != outData[i][0]:
            return False
    return True

def merge(A, left, mid, right):

    n1 = mid - left
    n2 = right - mid
    
    L = list(range(n1+1))
    R = list(range(n2+1))
    
    for i in range(n1):
        L[i] = A[left + i]
    for i in range(n2):
        R[i] = A[mid + i]
        
    L[n1] = ['ban', 100000000000]
    R[n2] = ['ban', 100000000000]
    
    i = 0
    j = 0
    
    for k in range(left, right):
        if L[i][1] <= R[j][1]:
            A[k] = L[i]
            i = i + 1
            
        else:
            A[k] = R[j]
            j = j + 1
            
    return
            
def mergeSort(A, left, right):
    count = 0
    if left+1 < right:
        mid = int((left + right) / 2)
        mergeSort(A, left, mid)
        mergeSort(A, mid, right)
        merge(A, left, mid, right)

    return


import sys
import copy

n = int(sys.stdin.readline())
a = []
for _ in range(n):
    tin = list(sys.stdin.readline().split())
    a.append([tin[0], int(tin[1])])
b = copy.deepcopy(a)

key = quickSort(a, 1, n -1)
mergeSort(b, 0, n)

if isStable(a, b, n):
    print('Stable')
else:
    print('Not stable')

for _ in range(n):
    print(*a[_])

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



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

def merge(list1, list2):
    output = []
    p1 = 0
    p2 = 0
    l1 = len(list1)
    l2 = len(list2)
    while p1 < l1 and p2 < l2:
        if list1[p1][0] <= list2[p2][0]:
            output.append(list1[p1])
            p1 += 1
        else:
            output.append(list2[p2])
            p2 += 1
    return output + list1[p1:] + list2[p2:]



def merge_sort(cards):
    if len(cards) <= 1:
        return cards
    else:
        pivot = len(cards)//2
        return merge(merge_sort(cards[:pivot]), merge_sort(cards[pivot:]))
        
quick = cards.copy()
quick_sort(quick, 0, len(quick)-1)
merge = merge_sort(cards)

for i in range(n):
    if quick[i][1] != merge[i][1]:
        print("Not stable")
        break
else:
    print("Stable")

for num, sign in quick:
    print( sign + ' ' + str(num))

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

def 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().split() for i in range(n)]
a_before=a[:]
quickSort(a,0,n-1)
isStable=True
for i in range(1,n):
    if a[i][1]==a[i-1][1] and a_before.index(a[i])<a_before.index(a[i-1]):
        isStable=False
        break
if isStable:
    print("Stable")
else:
    print("Not stable")
for i in a:
    print(" ".join(i))

Solution (Python):
from copy import copy

def merge(arr, left, middle, right):
    L = arr[left:middle]
    L.append([None, float('inf')])
    R = arr[middle:right]
    R.append([None, float('inf')])

    iterL, iterR = iter(L), iter(R)
    l,r = next(iterL), next(iterR)

    for index in range(left, right):
        if l[1] <= r[1]:
            arr[index] = l
            l = next(iterL)
        else:
            arr[index] = r
            r = next(iterR)


def merge_sort(arr, left, right):
    if left + 1 < right:
        pivot = (left + right) // 2
        merge_sort(arr, left,  pivot)
        merge_sort(arr, pivot, right)
        merge(arr, left, pivot, right)


def partition(arr, start, end):
    criteria = arr[end][1]
    idx1 = start
    for idx2 in range(start, end):
        if arr[idx2][1] <= criteria:
            arr[idx1],arr[idx2] = arr[idx2],arr[idx1]
            idx1 += 1
    arr[idx1],arr[end] = arr[end],arr[idx1]
    return idx1

def quick_sort(arr, start, end):
    if start < end:
        pivot = partition(arr, start, end)
        quick_sort(arr, start, pivot - 1)
        quick_sort(arr, pivot +1, end)


num = int(input())
arr = []
for index in range(num):
    sign, number = input().split()
    arr.append([sign, int(number)])

arr1 = copy(arr)
arr2 = copy(arr)

merge_sort(arr1, 0, num)
quick_sort(arr2, 0, num - 1)

print("Stable" if arr1 == arr2 else "Not stable")
for sign, number in arr2:
    print(sign + " " + str(number))

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

quickSort(data,0,n-1)

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

for i in data:
    print(' '.join(str(d) for d in i))

Solution (Python):
import sys, os, math, bisect, itertools, collections, heapq, queue, copy, array
from typing import List





sys.setrecursionlimit(10000000)

ii = lambda: int(sys.stdin.buffer.readline().rstrip())
il = lambda: list(map(int, sys.stdin.buffer.readline().split()))
fl = lambda: list(map(float, sys.stdin.buffer.readline().split()))
iln = lambda n: [int(sys.stdin.buffer.readline().rstrip()) for _ in range(n)]

iss = lambda: sys.stdin.buffer.readline().decode().rstrip()
sl = lambda: list(map(str, sys.stdin.buffer.readline().decode().split()))
isn = lambda n: [sys.stdin.buffer.readline().decode().rstrip() for _ in range(n)]

lcm = lambda x, y: (x * y) // math.gcd(x, y)

MOD = 10 ** 9 + 7
MAX = float('inf')


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


def partition(cards: List[Card], p: int, r: int) -> int:
    x = cards[r].value
    i = p - 1
    for j in range(p, r):
        if cards[j].value <= x:
            i += 1
            cards[i], cards[j] = cards[j], cards[i]
    cards[i + 1], cards[r] = cards[r], cards[i + 1]
    return i + 1


def quick_sort(cards: List[Card], p: int, r: int):
    if p < r:
        q = partition(cards, p, r)
        quick_sort(cards, p, q - 1)
        quick_sort(cards, q + 1, r)


def merge(cards: List[Card], left: int, mid: int, right: int):
    n1 = mid - left
    n2 = right - mid
    L, R = [Card('Z', 0)] * (n1 + 1), [Card('Z', 0)] * (n2 + 1)
    for i in range(n1):
        L[i] = cards[left + i]
    for i in range(n2):
        R[i] = cards[mid + i]

    L[n1] = Card('Z', float('INF'))
    R[n2] = Card('Z', float('INF'))

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


def merge_sort(cards: List[Card], left: int, right: int):
    if left + 1 < right:
        mid = (left + right) // 2
        merge_sort(cards, left, mid)
        merge_sort(cards, mid, right)
        merge(cards, left, mid, right)


def main():
    if os.getenv("LOCAL"):
        sys.stdin = open("input.txt", "r")

    N = ii()
    A, B = [], []
    for n in range(N):
        suit, value = sl()
        A.append(Card(suit, int(value)))
        B.append(Card(suit, int(value)))

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

    
    for a, b in zip(A, B):
        if a.suit != b.suit or a.value != b.value:
            print('Not stable')
            break
    else:
        print('Stable')
    for a in A:
        print(a.suit, a.value)


if __name__ == '__main__':
    main()

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 main():
    n = int(input())
    A = []

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

    quick_sort(A, 0, n - 1)

    flag = False
    for i in range(1, n):
        if A[i - 1][1] == A[i][1]:
            if A[i - 1][2] > A[i][2]:
                flag = True
                break

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

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


if __name__ == "__main__":
    main()

Solution (Python):
import math

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

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

class Card(str):
    def __init__(self, input_card):
        super().__init__
        self.num = int(input_card.split(" ")[-1])

N = int(input().rstrip())
A = []
for _ in range(N):
    A.append(Card(input().rstrip()))

A_2 = A.copy()

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

stable = True
for a_1, a_2 in zip(A, A_2):
    if a_1 != a_2:
        stable = False
        break
print("Stable" if stable else "Not stable")
for a in A:
    print(a)

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

if __name__ == '__main__':
  N = int(input())
  A=[]
  B=[]
  for _ in range(N):
    s, n = input().split()
    A.append((s, int(n)))
    B.append((s, int(n)))

  def swap(A, i, j):
    tmp = A[i]
    A[i] = A[j]
    A[j] = tmp
  
  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
        swap(A, i, j)
    swap(A, i + 1, r)
    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(B, left, middle, right):
    n1 = middle - left
    n2 = right - middle
    L1=[('a', 0)]*n1
    L2=[('a', 0)]*n2
    for i in range(n1):
      L1[i] = B[left + i]
    for j in range(n2):
      L2[j] = B[middle + j]
    L1.append(('z', 10**9+1))
    L2.append(('z', 10**9+1))
    
    
    i = 0
    j = 0
    for k in range(left, right):
      if L1[i][1] <= L2[j][1]:
        B[k] = L1[i]
        i += 1
      else:
        B[k] = L2[j]
        j += 1

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

  
  quicksort(A, 0, N - 1)
  mergeSort(B, 0, N)
  print('Stable' if A==B else 'Not stable')
  for a in A:
    print(a[0] + ' ' + str(a[1]))

Solution (Python):
import sys

sys.setrecursionlimit(10**6)


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

    N = int(sys.stdin.readline().rstrip())

    A = []

    for i in range(N):
        m, n = sys.stdin.readline().rstrip().split()
        A.append((m, int(n), i))  

    quicksort(A, 0, N - 1)

    for i in range(1, N):
        if A[i][1] == A[i - 1][1]:
            if A[i][2] < A[i - 1][2]:
                print("Not stable")
                break
    else:
        print("Stable")

    for m, n, _ in A:
        print(m, n)


main()

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)
    return None
        
n = int(input())
A = [(i,int(j)) for i,j in [input().split() for i in range(n)]]
B = A.copy()
quickSort(A,0,n-1)
num = A[0][1]
pos = B.index(A[0])
ans = "Stable"
for i in A[1:]:
    if i[1] != num:
        num = i[1]
        pos = B.index(i)
    else:
        if pos > B.index(i):
            ans = "Not stable"
            break
        else:
            pos = B.index(i)
print(ans)
for i,j in A:
    print(i,j)

Solution (Python):
from copy import deepcopy
 
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())
cards = []
for i in range(n):
    card = input().split()
    card[1] = int(card[1])
    cards.append(card)
prev_cards = deepcopy(cards)
prev_cards.sort(key=lambda card: card[1])
 
Quicksort(cards, 0, n-1)
 
if cards == prev_cards:
    print("Stable")
else:
    print("Not stable")
 
for card in cards:
    print(' '.join(map(str, card)))

Solution (Python):
n = int(input())
suits = [0] * n
ranks = [0] * n
orders = [0] * n
for i in range(n):
    suit, rank = input().split()
    suits[i] = suit
    ranks[i] = int(rank)
    orders[i] = i

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

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

quicksort(0, n-1)

for i in range(1, n):
    if ranks[i] == ranks[i-1] and orders[i] < orders[i-1]:
        print('Not stable')
        break
else:
    print('Stable')

for i in range(n):
    print(suits[i], ranks[i])

Solution (Python):

"""
ソートテク関連の基本的な関数の詰め合わせ (命名は C++ STL algorithm による)


stable_partition(seq, func):
    O(n)
    空間計算量も O(n)
    述語が True を返す全ての要素が、述語が False を返す全ての要素よりも前になるようにシーケンスを並び替える (破壊、安定)


nth_element(seq, k, begin, end):
    O(n)
    E = seq[k] とする
    特定の要素 E よりも小さい全ての要素が E よりも前になり、 E 以上の全ての要素がEよりも後になるように seq[begin:end] を並び替える (破壊、不安定)
    heapq の nlargest とは異なるので注意


ith_order_statistic(seq, i, begin, end):
    O(n)
    nth_element を用いて (seq[begin:end] に存在することがわかっている) i 番目の順序統計量を求める (i = 0, 1, ..., n-1)


simple_quick_sort(seq, begin, end):
    O(nlgn)
    nth_element を用いて seq[begin:end] をソートする (破壊、不安定)


modified_merge_sort(seq, begin, end):
    O(nlgn)
    _modified_merge を用いて seq[begin:end] をソートする (非破壊、安定)
    転倒数とソート済み配列を返す


count_inversion(seq):
    O(nlgn)
    modified_merge_sort を用いて seq の転倒数を求める
    (転倒数: seq[i] > seq[j] (i < j) なる (i, j) の組み合わせの数のこと)
"""


import random
from typing import TypeVar, Callable, List, Tuple, Union
T = TypeVar('T')
Num = Union[int, float]




import random
from typing import TypeVar, Callable, List, Tuple, Union
T = TypeVar('T')
Num = Union[int, float]



def nth_element(L: List[Num], pivot_ind: int, begin: int=-1, end: int=-1, key=lambda x: x) -> int:
    """
    pivot = L[pivot_ind] とする。 'pivot 未満の要素 ... pivot ... pivot 以上の要素' となるよう L を破壊的に並び替える。(O(n))
    最後に基準値の pivot がおさまった場所のインデックスを返す。
    begin <= pivot_ind < end の要請はあるが、begin, end の指定により L[begin:end] に対象を絞り L[pivot_ind] 未満 / 以上に並べ替えることもできる。

    Args:
        L (list)
        pivot_ind (int)
        begin, end (int): L の [begin, end) 半開区間を考える。デフォルトでは L[0:n] となる

    Returns:
        int: 最後に基準値の pivot がおさまった場所のインデックス

    Examples:
        >>> seq = [1, 9, 2, 7, 5, 6, 4, 8, 3, 0]
        >>> nth_element(seq, 4)
        5
        >>> seq
        [1, 2, 0, 4, 3, 5, 7, 8, 9, 6]
        >>> nth_element(seq, 3, begin=3, end=9)
        4
        >>> seq
        [1, 2, 0, 3, 4, 5, 7, 8, 9, 6]
    """
    if begin == -1 and end == -1:
        begin, end = 0, len(L)
    if not begin <= pivot_ind < end:
        raise RuntimeError(f"nth_element(): pivot_ind should be begin <= pivot_ind < end. got pivot_ind={pivot_ind}, begin={begin}, end={end}.")

    
    end -= 1
    pivot = L[pivot_ind]
    L[pivot_ind], L[end] = L[end], L[pivot_ind]
    
    i = begin - 1
    
    
    for j in range(begin, end):
        if key(L[j]) <= key(pivot):
            i += 1
            L[j], L[i] = L[i], L[j]
    L[i+1], L[end] = L[end], L[i+1]
    return i+1




def simple_quick_sort(L: List[Num], begin: int, end: int, key=lambda x: x) -> None:
    """
    nth_element 関数を用いて L[begin:end] を 破壊的に不安定でクイックソートする O(nlgn)

    Args:
        L (list)
        begin, end (int)
    
    Examples:
        >>> seq = [3, 5, 2, 1, 0, 3]
        >>> simple_quick_sort(seq, 0, 6)
        >>> seq
        [0, 1, 2, 3, 3, 5]
    """
    if end - begin > 1:
        
        
        mid = nth_element(L, end - 1, begin, end, key)
        simple_quick_sort(L, begin, mid, key)
        simple_quick_sort(L, mid+1, end, key)



def _modified_merge(left: List[Num], right: List[Num], key=lambda x: x) -> Tuple[int, List[Num]]:
    """
    ソート済み配列 left, right を受け取り、全体のソート済み配列を生成する (O(n))
    マージの過程で転倒数をメモして返す

    Args:
        left (list): ソート済み
        right (list): ソート済み

    Returns:
        inv (int): 転倒数
        sorted_list (list): ソート済み
    
    Examples:
        >>> _modified_merge([1, 5, 7], [2, 3, 3])
        (6, [1, 2, 3, 3, 5, 7])
    """
    sorted_list = []
    i, j, inv = 0, 0, 0
    buf_1 = left[:] + [[None, float('inf')]]
    buf_2 = right[:] + [[None, float('inf')]]
    for _ in range(len(left) + len(right)):
        if key(buf_1[i]) <= key(buf_2[j]):
            sorted_list.append(buf_1[i])
            i += 1
        else:
            sorted_list.append(buf_2[j])
            j += 1
        inv += 1
    return inv, sorted_list




def modified_merge_sort(L, begin, end, key=lambda x: x):
    """
    L[begin:end] を 非破壊的かつ安定にマージソートする (O(nlgn))
    マージソートの過程で転倒数をメモして返す

    Args:
        L (list)
        begin, end (int)
    
    Returns:
        inv (int): 転倒数
        sorted_list (list): ソート済み
    
    Examples:
        >>> modified_merge_sort([3, 5, 2, 1, 0], 0, 5)
        (9, [0, 1, 2, 3, 5])
    """
    if end - begin == 1:
        return 0, [L[begin]]
    mid = (begin + end) // 2
    left_inv_cnt, left = modified_merge_sort(L, begin, mid, key)
    right_inv_cnt, right = modified_merge_sort(L, mid, end, key)
    merge_inv_cnt, sorted_list = _modified_merge(left, right, key)
    return left_inv_cnt + right_inv_cnt + merge_inv_cnt, sorted_list





if __name__ == "__main__":
    n = int(input())
    L = []
    for _ in range(n):
        char, num = input().split()
        num = int(num)
        L.append([char, num])
    _, stable_seq = modified_merge_sort(L, 0, n, key=lambda x: x[1])
    simple_quick_sort(L, 0, n, lambda x: x[1])
    
    print('Stable') if stable_seq == L else print('Not stable')
    
    
    for elm in L:
        print(*elm, sep=' ')

Solution (Python):
import sys
def input():
    return sys.stdin.readline()[:-1]
    
n = int(input())
A = []

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

def check_stable(A):
    for i in range(n-1):
        if (A[i][1] == A[i+1][1]) & (A[i][2]>A[i+1][2]):
            return "Not stable"
    return "Stable"

print(check_stable(A))

for a,num,_ in A:
    print(*[a, num])

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


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


def resolve():
    from collections import defaultdict, deque
    n = int(input())
    A = []
    chk = defaultdict(deque)
    for _ in range(n):
        a, b = input().split()
        b = int(b)
        A.append([a, b])
        chk[b].append(a)
    quickSort(A, 0, len(A) - 1)
    for a, b in A:
        if chk[b].popleft() != a:
            print("Not stable")
            break
    else:
        print("Stable")
    for a in A:
        print(*a)


resolve()

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


deck = []
n = int(input())
for index in range(n):
  mark, number = input().split()
  card = [mark, int(number), index]

  deck.append(card)

quickSort(deck, 0, n-1)

ans = 'Stable'
for i in range(1, n):
  if deck[i-1][1] == deck[i][1]:
    if deck[i-1][2] > deck[i][2]:
      ans = 'Not stable'
      break
print (ans)
for v in deck:
  print ('{mark} {number}'.format(mark=v[0], number=v[1]))

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)

n = int(input())
A = []
for i in range(n):
    x, y = input().split()
    A.append([x, int(y)])
    
B = A[:]

quickSort(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(*i)

Solution (Python):
import sys, copy
input = lambda: sys.stdin.readline().rstrip() 
sys.setrecursionlimit(10**7)
INF = 10**10
def I(): return int(input())
def F(): return float(input())
def SS(): return input()
def LI(): return [int(x) for x in input().split()]
def LI_(): return [int(x)-1 for x in input().split()]
def LF(): return [float(x) for x in input().split()]
def LSS(): return input().split()

def resolve():
    n = I()
    A = []
    for _ in range(n):
        SN = LSS()
        A.append((SN[0], int(SN[1])))

    A_org = copy.deepcopy(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 is_stable(A, A_org):
        

        d_A = {}
        for i in A:
            if i[1] in d_A:
                d_A[i[1]].append(i[0])
            else:
                d_A[i[1]] = [i[0]]
        d_A_org = {}
        for i in A_org:
            if i[1] in d_A_org:
                d_A_org[i[1]].append(i[0])
            else:
                d_A_org[i[1]] = [i[0]]

        if d_A == d_A_org:
            return 'Stable'
        else:
            return 'Not stable'

    quickSort(A, 0, n-1)
    print(is_stable(A, A_org))
    for s, n in A:
        print(s, n)

if __name__ == '__main__':
    resolve()

Solution (Python):


import copy


def partition(A, p, r):
    x = int(A[r].split()[1])

    i = p - 1
    tmp = 0

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


def checkStable(before_list, sorted_list):

    for val in sorted_list:
        same_list = [
            i for i in sorted_list
            if (int(val.split()[1]) == int(i.split()[1])) and val != i
        ]
        if len(same_list) == 0:
            continue

        for data in same_list:
            bef = before_list.index(val) - before_list.index(data)
            aft = sorted_list.index(val) - sorted_list.index(data)

            if (bef > 0 and aft < 0) or (bef < 0 and aft > 0):
                return 'Not stable'

    return 'Stable'


if __name__ == "__main__":
    n = int(input())

    A = []
    for _ in range(n):
        A.append(input())

    bef_A = copy.deepcopy(A)

    aft_A = quickSort(A, 0, n - 1)

    print(checkStable(bef_A, aft_A))

    for data in aft_A:
        print(data)

Solution (Python):
import sys
import itertools
sys.setrecursionlimit(1000000000)
from heapq import heapify,heappop,heappush,heappushpop
import math
import collections
import copy


def Partition(A,p,r):
    x = A[r][1]
    i = p - 1
    for j in range(p,r):
        if A[j][1] <= x:
            i = i + 1
            tmp = A[i]
            A[i] = A[j]
            A[j] = tmp
    tmp2 = A[i+1]
    A[i+1] = A[r]
    A[r] = tmp2
    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())
    card = []
    for i in range(n):
        key,val = input().split()
        card.append([key,int(val)])
    card2 = copy.copy(card)
    card2.sort(key= lambda x:x[1])
    QuickSort(card,0,n-1)
    if card2 == card:
        print("Stable")
    else:
        print("Not stable")
    for i in range(n):
        print(card[i][0],card[i][1])

Solution (Python):
n=int(input())
nums=[input().split() for i in range(n)]
for j in range(n):
    nums[j][1]=int(nums[j][1])
    nums[j].append(int(j))


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

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

quick_sort(nums,0,n-1)

key=1

for i in range(n):
    if i!=n-1:
        if nums[i][1]==nums[i+1][1]:
            if nums[i][2]>nums[i+1][2]:
                key=0

if key:
    print("Stable")

else:
    print("Not stable")

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

Solution (Python):
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 = 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 i in range(n)]
stable = sorted(A, key=lambda x:
int(x.split()[1]))
B = A[:]
quicksort(A,0,n-1)
print("Stable" if stable == A else "Not stable")

for c in A:
    print(c)

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())
cards = [input() for i in range(n)]
stable = sorted(cards, key=lambda x: int(x.split()[1]))
quick_sort(cards, 0, n - 1)

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

for card in cards:
    print(card)

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())
cards = [input() for i in range(n)]
stable = sorted(cards, key=lambda x: int(x.split()[1]))
quick_sort(cards, 0, n - 1)

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

for card in cards:
    print(card)