a sorting question!
Background:
I've got a list of ~500 scrum tasks with a coarse priority (very high, high, medum, low, very low) and of course unique ids. Using those, I can define an ordering based on: Sort by coarse priority if different Sort by unique id otherwise.
I then want to allow my users to modify the order, moving tasks around (mostly within the same coarse buckets, but potentially even putting some very low tasks ahead of very high tasks). This is an ongoing process; the exact ordering might change every day.
In addition that that ongoing process, every day new tasks are added to the backlog. I want a way to intelligently find the "appropriate" index into the user-sorted list for the new tasks.
Proposed algorithm:
Call the well-defined but not very good sort order Alpha. Call the user-defined (and hence unknown) but authoritative sort order Beta.
When adding a new element, Find index that maximizes value(index):
value(index): Assign +1 point for each element that occurs before index in the beta sort order and that occurs before the new element in the Alpha sort order. Assign -1 point for each element that occurs before index in the beta sort order and that occurs after the new element in the Alpha sort order.
Insert the new element at index.
Is there a more "correct" algorithm? Note runtime here is O(n) for each insertion, since you can calculate the value(index+1) in constant time given value(index).