a collection data structure to keep items sorted

Question

I got a program which is using an ArrayList<T> and that type T also implements Comparable<T>. I need to keep that list sorted.

For now, when I insert a new item, I add it to the ArrayList and then invoke Collections.sort(myArrayList).

Is sorting with Collections.sort every time I insert a new item seriously hurt run time complexity?

Is there a better suited data structure I can use to always keep the list sorted? I know of a structure called a PriorityQueue but I also need to be able to get the list's elements by index.

EDIT: In my specific case, inserting a new item happens much less than geting an already existing item, so eventually a good advice could also be to stay with the ArrayList since it got a constant time complexity of getting an item. But if you know of anything else...

Answer 1

It seems like Collection.Sort is actually the way to go here since when the collection is already almost sorted, the sorting will take not longer than O(n) in the worst case.