組み込み開発のためのPython · レッスン 165 / 220
マージソートを理解する
マージソートは分割した配列を整列しながら統合するO(n log n)の方法です。安定性を保ちやすい一方、追加メモリが必要です。
マージソートは分割した配列を整列しながら統合するO(n log n)の方法です。安定性を保ちやすい一方、追加メモリが必要です。 仕組みだけでなく、検証方法と運用上の注意も具体例で確認します。
基本の考え方
マージソートは分割した配列を整列しながら統合するO(n log n)の方法です。安定性を保ちやすい一方、追加メモリが必要です。
安全に試すための確認
計算量だけでなく入力条件、重複値、空データ、最悪ケースを確かめます。組み込み用途ではメモリ上限と実行時間を実測し、標準ライブラリの利用も検討してください。
コード例
手元のPython環境に貼り付ける前に、使用しているPythonの版と対象ライブラリの対応を確認してください。
def merge(left, right):
result = []
while left and right:
result.append(left.pop(0) if left[0] <= right[0] else right.pop(0))
return result + left + right
print(merge([1, 4], [2, 3]))手を動かす課題
安定なマージ処理を実装し、同じキーを持つレコードの元の順番が保たれることを確認してください。