If the number of elements is large, the better option would be an array (or any type that has contiguous memory storage, i.e. a std::vector
, allocating with new []
, etc.). A linked list usually does not store its nodes in contiguous memory. The contiguous memory aspect leads to better cache friendliness.
In addition to this, a linked list (assuming a doubly-linked list), would need to store a next
and previous
pointers to the next and previous elements for each data item, thus requiring more memory per data item. Even for a singly-linked list, a next
pointer has to exist, so even though less overhead than a doubly-linked list, it is still more overhead than an array.
Another reason that isn't related to efficiency why you want to use an array is ease of implementation of the sorting algorithm. It is more difficult to implement a sorting algorithm for a linked list than it is for an array, and especially an algorithm that works with non-adjacent elements.
Also, please note that std::sort
is an algorithm, it is not a container. Thus it can work with regular arrays, std::array
, std::vector
, std::deque
, etc. So comparing std::sort
to an array is not a correct comparison.