Insertion sort can be optimized by the binary search to find out where to insert the element sorted partition. I wonder the time complexity of binary insertion sort with linked list is O(n log n) here.
Here is my pseudo code:
for each tail: 1. linearSearch(headIndex++, tailIndex, tailValue) or 2. binarySearch(headIndex++, tailIndex, tailValue) if element is found : insert tail rightly before head;
For linear search, it is obvious that the time complexity is O(n^2).
For binary search, I wonder if the time complexity is dependent on what data structure we are using here. Here is my take:
In the case of array, the time complexity is still O(n^2) with binary search, since the the insertion is implemented by the consecutive swap from tail to head position which takes O(n) swaps, therefore though the binary search part is O(log n), the swap is the bottleneck.
In the case of list, the time complexity can be reduced to O(n log n), since the insertion cost is O(1) now, the bottle neck becomes the binarySearch O(log n).