Space complexity of C# sort on string lists

Question

I'm implementing a program to sort large files that maybe don't fit in memory. All files will be sorted by lines so I'm thinking in use a List to do it.

I already calculated how many lines I can have in memory to split the files in smaller files, but I don't know how many space I need in memory to sort a List of N elements.

The question is, knowing the maximum number of elements (strings of known size) and the available memory, how much space in memory will the List.Sort method will need?

Answer 1

List<T>.Sort uses a quicksort algorithm, which is O(log n) space.

http://en.wikipedia.org/wiki/Quicksort#Space_complexity

Answer 2

Quick sort is O(logn) space complexity, because it stores constant information (beginning and end of the partition) at every recursive level, and there's at most logn levels.

The merge itself is in-place, as is the bubble sort fallback, so they're O(1) and as such don't count.

Answer 3

Do some research: List.Sort() uses the QuickSort algorithm by default, which has O(logn) space complexity.

If you are really worried about space complexity and don't mind a slower algorithm you could use Bubble sort which has O(1) space complexity.