1025-MergeSort

Cerința

Se dă un șir cu n elemente, numere întregi. Folosind metoda MergeSort (Sortare prin interclasare), ordonați crescător elementele acestui șir.

Date de intrare

Programul citește de la tastatură numărul n, iar apoi cele n elemente ale șirului.

Date de ieșire

Programul va afișa pe ecran elementele șirului sortat, separate prin exact un spațiu.

Restricții și precizări

1 ≤ n ≤ 100.000
elementele șirului vor fi cuprinse între -1.000.000.000 și 1.000.000.000

Exemplu

Intrare

12
10 0 -1 -3 1 -4 9 3 -1 -4 3 -4 

Ieșire

-4 -4 -4 -3 -1 -1 0 1 3 3 9 10

Rezolvare

<syntaxhighlight lang="python" line>

def mergeSort(array):

   if len(array) > 1:

       #  r is the point where the array is divided into two subarrays
       r = len(array)//2
       L = array[:r]
       M = array[r:]

       # Sort the two halves
       mergeSort(L)
       mergeSort(M)

       i = j = k = 0

       # Until we reach either end of either L or M, pick larger among
       # elements L and M and place them in the correct position at A[p..r]
       while i < len(L) and j < len(M):
           if L[i] < M[j]:
               array[k] = L[i]
               i += 1
           else:
               array[k] = M[j]
               j += 1
           k += 1

       # When we run out of elements in either L or M,
       # pick up the remaining elements and put in A[p..r]
       while i < len(L):
           array[k] = L[i]
           i += 1
           k += 1

       while j < len(M):
           array[k] = M[j]
           j += 1
           k += 1

1. Print the array

def printList(array):

   for i in range(len(array)):
       print(array[i], end=" ")
   print()

1. Driver program

if __name__ == '__main__':

   array_to_be_sorted = input('Introduceti o lista de numere, separate prin spatiu:')
   array_to_be_sorted = array_to_be_sorted.split()

   mergeSort(array_to_be_sorted)

   print("Sorted array is: ")
   printList(array_to_be_sorted)

</syntaxhighlight>