I assume you are following an approach similar to this MSDN sample. If so, then sorting happens based on the collection view's SortDescriptions. As long as the source collection is observable, the sort order should be respected when items are added or removed from the collection.
The real problem arises when an item is modified after being added to the collection. In that case, the collection is not automatically re-sorted.
I explain the issue in detail in 'E' is for Editable Collection (in my ItemsControl A to Z series). I also present a few workarounds that offer different levels of performance. The most drastic is to force a re-sort of the entire collection by calling Refresh() on the CollectionView. If possible, I would avoid that and use a better option, like implementing IEditableObject on your items and issuing an Edit() followed by Commit() whenever the properties change on an item.