Linked list sorted insert vs. Array Sort. Which is faster?

Question

I have a linked-list which sorts elements as they are inserted but that is somewhat slow when I have to sort 20,000+ elements. Is it normally faster/more efficient to add all the elements to an array/linked list and then sort afterwords. This is assuming the elements would be in no particular order so it wouldn't be partially ordered. I feel like it would be quicker to sort after since you're not traversing the list 20,000 times but I'm looking for some more clarification.

Answer 1

The data structure in use (Linked List vs Array) and the implementation you're using matters a lot.

With Arrays

it will be much faster to insert all elements in one go and then sort it. This is because inserting a new element in the middle of an array will cause the remainder of the array to be shifted. for e.g.

inserting 3 into [1,2,5,7,8]

will cause insertion of element 3 in 3rd spot (where 5 was). This will cause 5 to be copied into 4th spot, 7 to be copied into 5th spot and 8 to be copied into 6th spot.

This type of shuffling will happen every time you insert an element in sorted order and that's expensive.

With Linked List

The kind of shuffling we see with array will not happen in case of Linked List because insertion will only require you to update pointers for the preceding and following elements. for e.g.

inserting 3 into 1 -> 2 -> 5 -> 7 -> 8

will require you to update the "next" element pointer to 3 and the "next" element pointer of 3 to point to 5. Elements 1, 7 and 8 remain unchanged.

So it'll probably be the same cost whether you insert everything and then sort or insert one at a time in it's correct position.

The implementation matters

All this is theoretical discussion. The implementation you use matters a lot. So you should look at documentation of that implementation for understanding how it implements these operations.