Optimizing error-sorting method

Question

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);
        List<Log> errorsSorted = new List<Log>();
        for (int i = 0; i < errors.Count; i++)
        {
            bool inserted = false;
            for (int j = 0; j < errorsSorted.Count; j++)
            {
                if (errors[i].Date < errorsSorted[j].Date)
                {
                    List<Log> tempList = new List<Log>();
                    tempList.AddRange(errorsSorted.GetRange(j, 
                        errorsSorted.Count - j));

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

                    errorsSorted.RemoveRange(j+1, errorsSorted.Count - (j+1));

                    // move all bigger dates one place to the right..
                    foreach (Log log in tempList) 
                    {
                        errorsSorted.Add(log);
                    }
                    break;
                }
            }
            if (!inserted)
            {
                errorsSorted.Add(errors[i]); // No date is bigger, add at the end
            }
        }

Answer 1

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).

Answer 2

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);
LinkedList<Log> errorsSorted = new LinkedList<Log>();
foreach (Log error in errors) {
  LinkedListNode<Log> node = errorsSorted.Last;
  while (node != null && error.Date < node.Value.Date) {
    node = node.Previous;
  }
  if (node != null) {
    errorsSorted.AddAfter(node, error);
  } else {
    errorsSorted.AddFirst(error);
  }
}

This is the insertion sort, which has a worst case performance of O(n^2) and a best case performance of O(n). Note that it starts looking through the sorted list from the end instead of the beginning, which gives it the O(n) performance if the list is already sorted.