Would it be possible to improve the insertion sort algorithm's running time if a doubly-linked list was used instead of an array?

Thank you.

CodePudding user response：

No, not in a big-O sense anyway. There's a few variants of insertion sort so let's talk about the one where the left-side of the list is sorted in ascending order and the right side is unsorted. On each iteration we find the first (left-most) element in the unsorted list, call that x, and then iterate backwards through the sorted list to see where that element belongs. If the list is an array we pull out our new element and move items in the sorted list right until we find where the item belongs and we put it there. So we iterate through n items in the list and for each of those we iterate through the items in the sorted list which will be 0 items on the first iteration, 1 on the next, 2 after that, ... up to n so, on average, we're dong up to n/2 comparions/swaps for each of our n iterations for a total runtime of O(n^2).

If you make it a doubly-linked list instead the only thing that changes is that instead of moving items one to the right as you iterate through the sorted list you leave them where they are and then you drop your new item into place repairing the list instead. But it's still n/2 average comparisons and pointer de-references (to find the next node in the list) so the big-O runtime is the same. It's actually probably slower in real life as the pointer de-references are likely not cache-friendly and take more time that moving items one-right in an array.