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.
与恶龙缠斗过久,自身亦成为恶龙;凝视深渊过久,深渊将回以凝视…