How to insert multiple objects in sorted C# List by order, when I got CompareTo()

Question

My homework task: I got Generic list in C#, I sorted it with List.Sort when CompareTo() is implemented. I have another list of same structure objects and I need to insert them in my first sorted List, not add them to the end of list and the again List.Sort, but Insert instantly in sorted and have sorted list after inserting. How should I do that? Long story short: I can't use SortedList, just Generic List, and I can't add my items to the end of MyList1 and then MyList1.Sort() My Lists look like:

List<MyClass> MyList1 = new List<MyClass>():
List<MyClass> MyList2 = new List<MyClass>()
MyList1.Sort();

And I need items from MyList2 insert into MyList1 by the same order it is sorted. My CompareTo() method, it sorts by two properties :

public int CompareTo(MyClass next)
{
    int pos = String.Compare(this.name, next.name, StringComparison.CurrentCulture);
    if ((this.price < next.price) || ((this.price== next.price) 
         && (pos > 0)))
    {
        return 1;
    }
    else 
    {
        return - 1;
    }
}

I figured out how it should look like, this works fine:

static void Inserting(List<MyClass> List1,
           List<MyClass> List2)
        {

            foreach (var item in List2)
            {
                var i = 0;
                while (i < List1.Count && item.CompareTo(List1[i]) > 0)
                    i++;
                List1.Insert(i, item);
            }

        }

Answer 1

You can override the List Add method and do it like the below example

public class MyClass : IComparable<MyClass>
{
    public string Name
    {
        get;
        set;
    }
    public int Desc
    {
        get;
        set;
    }

    public int CompareTo(MyClass other)
    {
        return Name.CompareTo(other.Name);
    }
}

public class MyList<T> : List<T> where T : IComparable<T>
{
    public new void Add(T item)
    {          
        if (base.Count == 0)
        {
            base.Add(item);
            return;
        }
        if (base[base.Count - 1].CompareTo(item) <= 0)
        {
            base.Add(item);
            return;
        }
        if (base[0].CompareTo(item) >= 0)
        {
            base.Insert(0, item);
            return;
        }
        int index = base.BinarySearch(item);
        if (index < 0)
            index = ~index;
        base.Insert(index, item);
        base.Add(item);
    }
}


   static void Main(string[] args)
    {
        MyClass myClass = new MyClass();
        myClass.Name = "B";
        MyClass myClass1 = new MyClass();
        myClass1.Name = "A";
        MyClass myClass2 = new MyClass();
        myClass2.Name = "C";
        MyClass myClass3 = new MyClass();
        myClass3.Name = "A";
        MyList<MyClass>mylist= new MyList<MyClass>();

        mylist.Add(myClass);
        mylist.Add(myClass1);
        mylist.Add(myClass2);
        mylist.Add(myClass3);
        Console.ReadKey();
    }

mylist will always be sorted here.

Answer 2

If you want to insert it at the correct position, you have three options:

1. find the correct position, then Insert it there
2. use a pre-sorted list such as SortedList<TKey,TValue> or SortedSet<T> (depending on your needs) and just add (note: SortedList<TKey,TValue> demands unique keys; SortedSet<T> applies unique values)
3. just AddRange() the second list and call Sort() again

The problem with "1" is that finding the correct position for each new element efficiently is awkward. If this were an array, you could use Array.BinarySearch - it returns a bitwise complement of the appropriate index if no match is found. You could implement a binary search on a List<T> manually, but.. that's not fun. For 1, you'd want to use BinarySearch which exists on the list (thanks @mjwills), noting that the return value when no match is found is a bitwise complement that tells you where to insert it. But you'll still need to do this for each element, which adds up.

Personally, I'd be tempted by SortedSet<T> or just calling AddRange() + Sort() on a List<T>