wiki:PythonExerciseMergeSortNonRecursive

Version 1 (modified by sgk, 13 years ago) (diff)

--

Python:練習問題:再帰呼び出しを使わずにマージソート

Python情報 >> Python練習問題

再帰呼び出しを使わずにマージソートを行うプログラムを作ってください。

マージソートというと再帰呼び出しがつきもののようです。 むしろ、プログラミング初心者向けの解説では、再帰呼び出しという概念の習得のためにマージソートが題材となっていることも多いようです。 でも、マージソートには再帰呼び出しは必須ではありません。 たまたま、マージソートのアルゴリズムが フラクタルのように自己相似な処理なので、再帰呼び出しを行うと素直に記述することができるだけです。

ここでは、再帰呼び出しを使わずにマージソートを作ってみましょう。 マージソートの仕組みを思い出してよくよく考えてください。 そもそもどんな処理を行うのが目的だったのか。

doctestを含んだスケルトンは、再帰呼び出しを使ったマージソートのページにあるのを使ってください。

解答例は、このページ上部のナビゲーションバーの「Browse Source」の中のどこかにあります。