Is there a way to generically quickly insert (log(n)) an item into any IList

Question

In WPF, I want to keep my ObservableCollection sorted. Items are added randomly and not in batch. I do not want to sort the entire IList each time. I want to insert at the proper place on each insert.

Is there a way to generically insert quickly (log(n)) an item into any IList of T.

Does anyone wrote the code for it?

Note: Yes, the list should already be sorted before calling this method.

Note2: Sometimes you have to use an IList and can't replace it with a SortedList and do not want to maintain 2 collections: For example: in WPF using an ObservableCollection.

Update, yes there is a way to do it. By using dichotomy. I ask the question to save me time. I'm writing it and will show it as soon as it is debugged.

Please, share your code and what you've tried. Right now your question is off-topic here — Pavel Anikhouski, May 19 '20 at 14:41
Since there are no complexity guarantees in the interface as it stands (e.g. no guarantee on the indexer being constant or linear), it's difficult to see how you can expect to implement something with guaranteed complexity building upon it. — Damien_The_Unbeliever, May 19 '20 at 14:46
@JoelCoehoorn, See question. I updated it to show you why I should not use a SortedList — Eric Ouellet, May 19 '20 at 15:02
@Pavel, why it is off topic? All LINQ is based on question like that? — Eric Ouellet, May 19 '20 at 15:03
@Damien_The_Unbeliever, I don't understand your comment. Anything that is sorted and have an indexer can have an insert function in log(n)? — Eric Ouellet, May 19 '20 at 15:05
You should just refer to the documentation (https://learn.microsoft.com/en-us/dotnet/standard/collections/#algorithmic-complexity-of-collections) on which collection type to use. Since `IList` is an interface and not the implementation the question itself does not make sense since it's dependent on the implementation type and not the interface being used. — Matthew, May 19 '20 at 15:09
@Pavel, I want to keep an ObservableCollection sorted (and keep good performance). So what's wrong in that? — Eric Ouellet, May 19 '20 at 15:10
@PavelAnikhouski, I edited my question, do you still maintain that my question is off-topic? — Eric Ouellet, May 19 '20 at 15:38
@Matthew, I updated my question, does it makes more sense to you now? — Eric Ouellet, May 19 '20 at 15:42
When I was younger I would bet one of my fingers that what you are trying to do is impossible. But after losing too many virtual fingers I have stopped doing that. Waiting to see your implementation. — Theodor Zoulias, May 19 '20 at 16:09
Related somehow: [How to perform a binary search on IList?](https://stackoverflow.com/questions/967047/how-to-perform-a-binary-search-on-ilistt) — Theodor Zoulias, May 19 '20 at 22:46
@EricOuellet a bit late, yea, sorry I didn't realize you were dealing with a list that was already sorted. — Matthew, May 22 '20 at 14:47

Eric Ouellet · Answer 1 · 2020-05-19T20:55:48.857

OK... I did it before someone would close my question (it almost happen with 2 votes to close)...

Although there was 2 persons who vote to close, I think it was a good question and I also think the code worth being kept.

It took me about 5 hours to do it and debug it. It seems to work fine. To save 5 hours... that's why I asked the question. To save time.

/// <summary>
/// Insert item in list in log(n). The list should already be sorted.
/// Item will be inserted and there will be duplicate if comparer return 0.
/// </summary>
/// <typeparam name="T"></typeparam>
/// <param name="list"></param>
/// <param name="item"></param>
/// <param name="comparer"></param>
/// <returns></returns>
public static int InsertInSortedList<T>(this IList<T> list, T item, Func<T, T, int> comparer = null)
{
    if (comparer == null)
    {
        comparer = Comparer<T>.Default.Compare;
    }

    int first = 0;
    int last = list.Count;
    int middle = 0;
    int compareResult = 0;

    if (last > 0)
    {
        while (true)
        {
            middle = first + ((last - first) / 2);

            compareResult = comparer(item, list[middle]);

            if (compareResult > 0)
            {
                first = middle + 1;

                if (first >= last)
                {
                    middle++;
                    break;
                } 

                continue;
            }

            if (compareResult < 0)
            {
                last = middle;

                if (first == last)
                {
                    break;
                }

                continue;
            }

            break;
        }
    }

    if (middle == list.Count)
    {
        list.Add(item);
    }
    else
    {
        list.Insert(middle, item);
    }

    return middle;

}

One note. In your implementation *O(log(n))* is the complexity of searching the index where new item must be inserted. But the operation of inserting new item into the list has its own complexity. For *List*, for example, complexity of inserting of new item at the position *i* involves shifting elements to the right of *i*. Therefore complexity of inserting of new item is *O(M)*, where *M <= N*. — Iliar Turdushev, May 19 '20 at 22:42
@IliarTurdushev, Mmmm, I should approve. I was wrong. Thanks for reminding me that! — Eric Ouellet, May 19 '20 at 22:46

score 1 · Accepted Answer · answered May 19 '20 at 22:42

Here are some useful extension methods for sorted IList<T> collections (SortedBinarySearch, SortedIndexOf, SortedInsert and SortedRemove). The binary search algorithm is stolen from the source code of the ArraySortHelper<T>.InternalBinarySearch method.

/// <summary>Searches within the sorted <see cref="IList{T}"/> for the
/// specified item and returns the zero-based index of the item if found;
/// otherwise, a negative number that is the bitwise complement of the index of
/// the next item that is larger than item or, if there is no larger item,
/// the bitwise complement of <see cref="IList{T}.Count"/>.</summary>
public static int SortedBinarySearch<T>(this IList<T> list, T item,
    IComparer<T> comparer = null)
{
    if (list == null) throw new ArgumentNullException(nameof(list));
    comparer = comparer ?? Comparer<T>.Default;

    int lo = 0;
    int hi = list.Count - 1;
    while (lo <= hi)
    {
        int i = lo + ((hi - lo) >> 1);
        int order = comparer.Compare(list[i], item);

        if (order == 0) return i;
        if (order < 0)
        {
            lo = i + 1;
        }
        else
        {
            hi = i - 1;
        }
    }
    return ~lo;
}

/// <summary>Searches for the specified item within the sorted
/// <see cref="IList{T}"/> and returns the zero-based index of the item
/// if found; otherwise, -1.</summary>
public static int SortedIndexOf<T>(this IList<T> list, T item,
    IComparer<T> comparer = null)
{
    int index = SortedBinarySearch(list, item, comparer);
    if (index < 0) return -1;
    return index;
}

/// <summary>Inserts an item into the sorted <see cref="IList{T}"/>.</summary>
public static int SortedInsert<T>(this IList<T> list, T item,
    IComparer<T> comparer = null)
{
    int index = SortedBinarySearch(list, item, comparer);
    if (index < 0) index = ~index;
    list.Insert(index, item);
    return index;
}

/// <summary>Removes an item from the sorted <see cref="IList{T}"/> and returns
/// true if the item is successfully removed; otherwise, false.</summary>
public static bool SortedRemove<T>(this IList<T> list, T item,
    IComparer<T> comparer = null)
{
    int index = SortedBinarySearch(list, item, comparer);
    if (index < 0) return false;
    list.RemoveAt(index);
    return true;
}

Is there a way to generically quickly insert (log(n)) an item into any IList

2 Answers2

Linked