Pseudocodice

Lezione 4 di 9 del corso Merge Sort - Serie DSA di Coddy.

mergeSort(array):
   if length(array) <= 1:
      return array
   mid = length(array) / 2
   left = mergeSort(array[0..mid])
   right = mergeSort(array[mid..end])
   return merge(left, right)

merge(left, right):
   result = []
   while left and right both still have elements:
      if left[0] <= right[0]:
         move the front of left into result
      else:
         move the front of right into result
   append whatever remains of left
   append whatever remains of right
   return result

Due funzioni lavorano insieme:

mergeSort continua a dividere l’array finché i pezzi non sono ordinati in modo banale, poi si affida a merge per combinarli.
merge esamina contemporaneamente due liste ordinate, prendendo sempre l’elemento più piccolo in testa, così la lista combinata rimane ordinata.

Provalo tu

Questa lezione non include una sfida di codice.