CODEWITHSUNDEEP
algorithmsortingdata-structures
Oded Sayar
Oded Sayar

Reputation: 429

What is the appropriate data structure for insertion sort?

I revisited insertion sort algorithm and noticed something funny.

One obviously shouldn't use an array with this sort, as upon insertion, one will have to shift all subsequent elements O(n^2 log(n)). However a linked list is also not good here, since we preferably find the right placement using binary search, which isn't possible for a simple linked list (so we end up with O(n^2)).

Which makes me wonder: what is a data structure on which this sorting algorithm provides its premise of O(nlog(n)) complexity?

Upvotes: 1

Views: 625

Answers (4)

Jean-Baptiste Yunès
Jean-Baptiste Yunès

Reputation: 36391

Insertion sort is defined over array or list, if you use some other data structure, then it will be another algorithm.

Of course if you use a BST, insertion and search would be O(log(n)) and your overall complexity would be O(n.log(n)) on the average (remind that it will be O(n^2) in the worst), but this will be no more an insertion sort but a tree sort. If you use an AVL tree, then you get the O(n.log(n)) worst case complexity.

Upvotes: 1

Ayan Sengupta
Ayan Sengupta

Reputation: 51

In insertion sort the best case scenario is when the sequence is already sorted and that takes Linear time and in the worst case takes O(n^2) time. I do not know how you got the logarithmic part in the complexity.

Upvotes: 0

Prune
Prune

Reputation: 77837

From where did you get the premise of O(n log n)? Wikipedia disagrees, as does my own experience. The premises of the insertion sort include components that are O(n) for each of the n elements.

Also, I believe that your claim of O(n^2 log n) is incorrect. The binary search is log n, and the ensuing "move sideways" is n, but these two steps are in succession, not nested. The result is n + log n, not a multiplication. The result is the expected O(n^2).

Upvotes: 2

btilly
btilly

Reputation: 46389

If you use a gapped array and a binary search to figure out where to insert things, then with high probability your sort will be O(n log(n)). See https://en.wikipedia.org/wiki/Library_sort for details.

However this is not as efficient as a wide variety of other sorts that are widely implemented. So this knowledge is only of theoretical interest.

Upvotes: 1

Related Questions