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