Pseudo Code
Coddyの「マージソート - DSAシリーズ」コースのレッスン 4/9。
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 result2つの関数が連携して動作します：
- mergeSort は、配列の要素がバラバラ（自明にソートされた状態）になるまで分割を繰り返し、その後 merge を利用してそれらを結合します。
- merge は2つのソート済みリストを同時に走査し、常に先頭の小さい方の要素を取り出すことで、結合後のリストがソートされた状態を維持するようにします。
自分で試してみよう
このレッスンにはコードチャレンジは含まれていません。
腕試しこのレッスンには短いクイズがあります。レッスンを始めて解答し、進捗を記録しましょう。
マージソート - DSAシリーズのすべてのレッスン
2The Algorithm
How it works?Pseudo CodeImplementation (Part 1)Implementation (Part 2)
Time and Space Complexity