How do I use merge sort to delete duplicates?

Question

I use recursive merge sort for sorting a link list, but during the merge sort I would like to delete duplicates. Anyone has insight in how to accomplish this?

I am using C code.

Answer 1

In merge sort you take two (or more) already-sorted lists repeatedly apply the following rules:

• find the lesser/least of the items of the top of each of the input lists, choosing any of the lowest items if there is a tie
• remove that item from its list
• add it to your output list

To remove duplicates, you simply modify the rules very slightly:

• find the lesser/least of the items of the top of each of the input lists, choosing any of the lowest items if there is a tie
• remove that item from its list
• if it is the same as the last item you added to your output list, throw it away
• otherwise, add it to your output list

This will ensure that no two consecutive items on your output list are the same, and that the items in it are in order, which is what you were after.