I have a lot of music and i want to rank them from least favorite to favorite (this will take many days). I would like to compare two music files at a time (2-way comparison). I saw some questions on algorithms with the fewest comparisons. But the catch is that (since it's a long process) i want to add new music to the collection and in that case i don't want to start over sorting everything (thus creating a lot more comparison steps).
Which algorithm has the least amount of comparisons while still allowing new elements to be added which need to be compared too?
I'm not interested in least amount of comparisons for just a few items. Let's say 1000 items minimum.
Bonus if the algorithm supports N-way comparison (where N > 2) in case i would like to compare pictures instead.
EDIT: comparing two songs are a manual process by listening to them (thus slowly), the sorting algorithm is needed to rank them in the fewest amount of comparisons
A non-comparative sorting algorithm, like radix sort, can sort data with 0 comparisons! These are not as generic as comparative sorting algorithms like merge or insertion sort, but can get far better runtime if your data meets the necessary requirements.
Essentially, if you have knowledge about the distribution of your data, you can sort faster than O(n log n). For instance, if you are sorting n numbers, and know that they are integers between 1 and N, you can use counting sort to sort them in O(n + N). You can iteratively add elements for O(1) as well.
Applying this to your problem of ranking music is more challenging (songs are not integers), but you can you do a variation of bucket sort where you first bin your music into, say, 10% "tiers": top 0-10%, 10-20%, 20-30%, ..., 90-100% (i.e., the bottom). Then you can either recursively apply bucket sort to those (top 0-1%, 1-2%, etc.) or apply standard sorting algorithms. Eventually, you'll need to do a standard comparison sort. This approach, compared with only using comparison sort, will reduce the number of comparisons by a factor of log(n)/log(n/B), where B is the number of buckets. For 100 buckets and 10000 songs, this is a factor of 2 reduction.
An alternative, comparison-saving approach is to do insertion sort (for both initial sorting and later insertions) with a modified binary search: instead of setting the initial bounds of the binary serach at 0 and n, set them to values based on your own intuition of where you are certain it will end up, like 0 and n/10, if it's definitely in your top 10%. The more granularly you can do this, the fewer comparisons you will need.
Caveat: with both bucket sort and the modified binary search, if you are wrong, you will need to do additional comparisons to fix your mistake.
And one final word: this question assumes that there exists is a correct ranking and that it can be achieved via comparisons. If you have circular preferences, such as a > b, b > c, and c > a, a la rock-paper-scissors, then a ranking cannot be constructed. The algorithms will still complete, but the resulting list will be inconsistent.