Should I use linked lists or arrays when sorting 100 million elements?

user_15396449 0
Viewed 119

I want to implement algorithms like quicksort, mergesort, etc., while working with a big data files, like 100 million elements. I can't use std::vector, std::sort, or anything like that, since this is a school assignment to get to know these specific algorithms. I can only use things that I will only write on my own.

Should I implement sorting algorithms using linked lists or arrays? Which from these two is more efficient in term of working with big data? What are the advantages of using one of them?

data-structures linked-list sorting arrays c++
1 Answers

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.

user_31333160
Related