What is the big O for a Dictionary's OrderBy method

Question

I am sorting a Dictionary of 10,000 elements using the OrderBy method as shown below and want to know the big O of it. Does anyone know? After Ordering them I then add them to a new Dictionary in that order. There might be a better way of doing this, but it works for my purposes.

Here is my example:

        m_sortedItems = new Dictionary<int,string>();
        foreach(KeyValuePair<int,string> item in collection.OrderBy(key => key.Value)){
            m_sortedItems.Add(item.Key, item.Value);
        }

I checked on msdn but it wasn't listed: http://msdn.microsoft.com/en-us/library/bb534966.aspx

Answer 1

Adding a sorted collection inside a regular dictionary makes no sense, since dictionary does not guarantee to mantain the order.This is just do discourage the code you shown in the question: it might works in some cases, but trust me it's not correct. It is necessary to point the fact that by adding the ordered set back to a dictionary will just vanify the sort you did before. You can enumerate the KeyValuePairs in some order and add in a regular list, that will preserve the insertion order, or better use some other data structures. Have a look for example at sorted dictionary. Of course such kind of data structures takes some more time in the insertion phase, while are generally fast in sorting because they are "naturally" ordered. As per documentation, sorted dictionary insertion time is "at best" O(log(n)), I suggest you to investigate the performance also for nearly ordered input set, because sometimes tree based data structures will suffer such situations due to unbalanced tree formation. If this is the case ( I'm not aware on how is implemented internally ) and performance becomes critical, another intersting data structure is the B-Tree.