Pseudokod

Lekcja 4 z 9 w kursie Sortowanie przez scalanie – seria DSA w 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

Dwie funkcje współpracują ze sobą:

mergeSort dzieli tablicę, aż jej części będą trywialnie posortowane, a następnie korzysta z merge, aby je połączyć.
merge jednocześnie przegląda dwie posortowane listy, zawsze wybierając mniejszy pierwszy element, dzięki czemu połączona lista pozostaje posortowana.

Spróbuj swoich sił

Ta lekcja nie zawiera wyzwania z kodem.