میدونیم که تو مرتب سازی درجی از جستجوی خطی استفاده میشه.وبدترین حالت میشه[tex]O(n^{2})[/tex]
حالامیشه به جای جستجوی خطی از جستحوی باینری استفاده کنیم تا زمان بدترین حالت بهبود پیداکنه و بشه[tex]O(nlgn)[/tex]?
جستجوی باینری رو هم میشه اضافه کرد اما مرتبه الگوریتم تغییری نمی‍کنه. چرا که به طور متوسط شما باید نصف اعضای لیست رو شیفت بدین.
در صورتی که از لیست پیوندی استفاده کنید پیچیدگی شیفت از بین می‍ره اما باید لیست پیوندی‍ای درست کنید که ایندکس داشته باشه و بتونید به وسط لیست به راحتی مراجعه کنید. فکر می‍کنم این کار باعث پیچیده شدن موضوع بشه در مجموع این‍طور بگم:
۱. در صورتی که از یک آرایه ساده استفاده می‍کنید همچنان پیچیدگی شیفت وجود داره و پیچیدگی الگوریتم همان [tex]O(n^2)[/tex] است.
۲. در صورتی که از لیست پیوندی استفاده می‍کنید نمی‍توانید از جستجوی باینری استفاده کنید! در این حالت پیچیدگی شیفت برابر ۱ است ولی پیچیدگی جستجو از مرتبه n است. بنابراین همچنان پیچیدگی الگوریتم [tex]O(n^2)[/tex] است.
۳. در صورتی که از لیست پیوندی ایندکس دار استفاده کنید. می‍تونید از جستجوی باینری استفاده کنید. در این حالت پیچیدگی شیفت هم برابر ۱ است اما نکته اینه که پیچیدگی به‍روز کردن ایندکس همچنان از مرتبه n است و در نتیجه پیچیدگی کلی الگوریتم باز هم [tex]O(n^2)[/tex] است.
در هر حال این الگوریتم در حالت کلی [tex]O(n^2)[/tex] است و کاریش هم نمی‍شه کرد!!