algorithm - sorting a partially sorted array with insertion sort

Question

N要素がソートされるまで最初の配列と、N + M要素がソートされないまでN + 1の配列があります（配列はN + M要素で構成されます）。挿入ソートを使用してこの配列をソートする複雑さは何ですか? (N+M)^2 だと思いますが、そうですか。

Answer 1

挿入ソートを使用する場合は、O（M *（M + N））操作が必要になります。ただし、より適切なアプローチは、ソートされていない部分をO（M * lgM）でソートしてから、2つのソートされた部分をO（N + M）でマージすることです。