ソートされていない配列内の各レコードは、ソートされた配列内の位置から最大で d << n の距離にあることが事前にわかっていると仮定します。この物件をぜひご利用いただきたいと思います。n 個のキーはすべて異なると仮定します。例: リストを 3 8 18 2 7 20 24 15 22 30 40 とします。このソートされていないリストでは、各レコードがソートされた配列内の位置から最大で 3 離れていることがわかります。
実行時間が O(n lg d) になる並べ替えを設計します。
課題質問です。いくつかのヒントが役立ちます。