# Optimizing error-sorting method

I just made this sort method. It runs fine and the code looks okay in my eyes.

Is is possible to optimize it so it runs faster? If it's $O(n^3)$ now, it would be interesting changing it to $O(n^2)$ or something like that.

Side question: This is $O(n^3)$, right (I only like $O(n^2)$ and below)?

List<Log> errors = _logHandler.GetErrors(daysBack);
for (int i = 0; i < errors.Count; i++)
{
bool inserted = false;
for (int j = 0; j < errorsSorted.Count; j++)
{
{
List<Log> tempList = new List<Log>();

errorsSorted[j] = errors[i]; // replace at bigger date index
inserted = true;

// move all bigger dates one place to the right..
{
}
break;
}
}
if (!inserted)
{
}
}

• Why aren't you using any of the built-in sorting methods?
– Jon Skeet
Nov 25, 2011 at 8:58
• Just make Log Comparable and then use the inbuilt method. Nov 25, 2011 at 9:02
• I did what was intuitive for me. I guess it's my skill cap. Nov 25, 2011 at 9:07
• I don't know if I can make it comparable, since the Log class is located in Log.designer.cs as a partial class. Maybe I should mention that I have a Log.dbml Nov 25, 2011 at 9:10
• I think for sort algorithms, you should rarely if ever accept anything with worse than O(n log n) runtime =)
– Jens
Nov 25, 2011 at 11:23

You are just sorting by date, correct? I'd use

using System.Linq;
// ....
List<Log> errors = _logHandler.GetErrors(daysBack);
List<Log> errorsSorted = errors.OrderBy(l => l.Date).ToList();


According to this stackoverflow question, OrderBy uses QuickSort in this case, which usually has a run time of O(n log n).

• Looks cool, I while check it out later to day when I get some spare time :) Nov 25, 2011 at 12:27
• Works very good and reduce the number of lines with 27 thanks :) Dec 2, 2011 at 8:21

Well, the obvious would be to use a better algorithm, i.e the built in:

errors.Sort((x,y) => x.Date.CompareTo(y.Date));


What you can do with your code is to use a more effective way to move the elements around. Right now you are moving items from one list to another to instert an item, but the List<T> class is itself capable of inserting an item. It will be a bit faster because you will only be copying the items once instead of twice for each insert.

Much better would be to use a linked list instead. It will be a lot faster because inserting an item will be O(1) instead of O(n) (where n is the number of items that needs to be moved). Something like this (not tested):

List<Log> errors = _logHandler.GetErrors(daysBack);
foreach (Log error in errors) {