Wednesday, June 12, 2013

C#: Inserting into sorted List

I wanted to have a sorted list, with the ability to have items duplicate, built in sorted collections doesn’t allow duplicate values, so I used a List, and for effeciancy, I maintained the items sorted in it while insertion, instead of calling the sort method with each insertion

To insert in the list sorted, I used the binary search method, to find the first item less then or equal to the inserted item

Suppose we have a sorted list “list”, and we want to insert item i keeping it sorted

List<int> list= new List<int>();

int index = list.BinarySearch(i);
if (index < 0)
set.Insert(~index, i);
set.Insert(index, i);