Calling a full sort routine on every insertion seems like overkill to me (especially quicksort, which is poor at almost sorted sets!). I can think of two approaches that will be better - which I'd prefer would depend on how I was expecting it to be used.
- On each insertion, work out the correct point of insertion and just insert there.
- Have a flag indicating whether the list is currently sorted correctly. On insertion, set it to false. Before any retrieve operation, if the flag is false sort the list before returning anything. After all, when you're not reading from the list you don't care if it's sorted or not.
(That's assuming you don't just want to search for an open source List that already does it)
If you can guarantee that the Vector* is always sorted, you can use a binary search (available in java.util.Collections) to find the location to add to. But note that you shouldn't really extend any List implementation, because you will break the contracts of List.add(E) and List.add(int, E). Both specify where in the List the new element should go, and you are not doing that.
Perhaps you should instead create a new Collection implementation that resembles a List but isn't so strict on the way the add methods should be implemented. Of course you can use a Vector (or ArrayList) internally to do all the hard work.
* Why use Vector as the base class? Why not use ArrayList? Unless you need synchronization ArrayList is always a better fit, and if you need synchronization you can also wrap an ArrayList using Collections.synchronizedList.
On each insertion, work out the correct point of insertion and just insert there
To insert an element at specific location is basically calling a sorting operation. so I have to call that logic for every insertion. Here is the problem.
Have a flag indicating whether the list is currently sorted correctly. On insertion, set it to false. Before any retrieve operation, if the flag is false sort the list before returning anything. After all, when you're not reading from the list you don't care if it's sorted or not.
This is a good idea but Sorted at Insertion and optimizing the insertion operation is what I am looking for.
Why use Vector as the base class?
I am not very specific to any existing Collections class. Vector was just an example. It can be my custom Vector or Arraylist that I want in Sorted.
Neither List nor Vector are suitable types for this, because they should allow the user to insert elements wherever they want.
You can implement your own SortedSet, or if you want to allow duplicate elements, you should implement your own Collection (SortedCollection maybe?).
If you want to keep the collection sorted at all times, you don't have to perform a sort operation on each insertion. You only have to perform a search operation on each insertion, and then insert the element in that position.
So algorithms like merge sort don't apply, you will need algorithms like binary search.