How can I add an element to a list that is sorted so that it keeps sorted?-CodePudding

Suppose I have a List<int> list that is sorted.

I want to add a new element x to the list so that it keeps sorted in the end.

Basically there would be 2 cases: if x > list[list.Count-1], then only list.Add(x) is needed.

Otherwise, a binary search would be needed for better performance, so I would be able to find an index i and call list.Insert(x, i). Is there anything ready that I can make use of?

Just to clarify the problem I'm solving.

There is a big list L and I have a window of size n that moves from the beginning to the end of L per iteration:

n = 4
L = 8 4 1 9 0 4 3 4 8 5 1 9 0 6 4 3 2 4
   [8 4 1 9]0 4 3 4 8 5 1 9 0 6 4 3 2 4   at i = 0
    8[4 1 9 0]4 3 4 8 5 1 9 0 6 4 3 2 4   at i = 1
    8 4[1 9 0 4]3 4 8 5 1 9 0 6 4 3 2 4   at i = 2
    8 4 1[9 0 4 3]4 8 5 1 9 0 6 4 3 2 4   at i = 3
    ...................................

and for each window, I have to sent the median of it to another function, so the most performant way I could thing of was sort the whole window in i = 0 and for each step in the iterations, I remove the first element and replace by a new one and call Sort again.

CodePudding user response：

You are describing List<T>.BinarySearch.

CodePudding user response：

I want to add a new element x to the list so that it keeps sorted in the end.

If you don't care about inserting it at the correct position and only that it is sorted when you're done, there's List.Sort.

Then just:

list.Add(x);
list.Sort();

If your object is more complex than an int you can provide a comparer.

CodePudding user response：

Use List<T>.FindIndex to find the index of the first item where x is greater. Then just insert as you normally would.

https://docs.microsoft.com/en-us/dotnet/api/system.collections.generic.list-1.findindex?view=net-6.0