#coding: cp852
#######################################
# Kr�tka implementacja merge sort z pokazem stabilno�ci.
#######################################

def merge(L,R):
  '''��czy listy L i R z zachowaniem porz�dku.'''
  (i,j)=[0]*2							# Ustawia pocz�tkowe po�o�enia obu wska�nik�w dla lewej i prawej listy. [0]*2=> [0,0] i dalej (i,j)=[0,0] jest r�wnowa�ne do i=0  oraz j=0. Oba wskazuj� na pierwsze elementy list.
  LL=len(L)							# Ustala d�ugo�� lewej cz��ci.
  LR=len(R)                                                     # Ustala d�ugo�� prawej cz��ci.
  RES=[]     							# pusty pojemnik na wyniki.
  while i<LL and j<LR:						# Dop�ki wska�niki s� przed ko=�cami list. Je�li cho� jedna lista jest pusta - ko�czy.
    if L[i][0]<=R[j][0]:					# Je�li pocz�tkowy element lewej listy ma zasadnicz� warto�� nie wi�ksz� od pierwszego prawej.
      RES+=[L[i]]						# Do wyniku dodaje pierwszy element lewej listy.
      i+=1							# Wska�nik idze do kolejnego elementu.
    else:							# je�li jest wiekszy.
      RES+=[R[j]]						# To samo z praw� list�.
      j+=1
  RES+=L[i:]+R[j:]						# Do wyniku dodaje nie zako�czon� list�.
  return RES                 					# Zwraca wynik.


def merge_sort(T):
  '''Sortuje list� t przez ��czenie.'''
  L=len(T)							# Ustala d�ugo�� listy.
  if L<=1:							# Je�li nie ma wi�cej ni� 1 element - jest pusta lub jednoelementowa - jest uporz�dkowana.
    return T							# Zwraca j�.
  i=L//2                    					# Ustala �rodek listy.
  return merge(merge_sort(T[:i]),merge_sort(T[i:]))		# ��czy posortowane merge_sort-em lew� i praw� po��wk�.



L1=[(5,0),(4,0),(6,0),(2,0),(33,0),(5,1),(22,0),(28,0),(55,0),(5,2),(37,0),(39,0),(49,0),(57,0)]
print(f'Przed sortowaniem {L1=}')
L2=merge_sort(L1)
print(f'Po sortowaniu {L2=}')