You can modify the Merge Sort algorithm to remove duplicates as well as sort the remaining items. One way to achieve this is to use a set to keep track of unique elements while performing the merge.
def merge_sort_and_remove_duplicates(arr):
if len(arr) <= 1:
return arr
# Split the array into halves
mid = len(arr) // 2
left_half = arr[:mid]
right_half = arr[mid:]
# Recursively sort and remove duplicates in each half
left_half = merge_sort_and_remove_duplicates(left_half)
right_half = merge_sort_and_remove_duplicates(right_half)
# Merge the sorted and deduplicated halves
return merge_and_remove_duplicates(left_half, right_half)
def merge_and_remove_duplicates(left, right):
result = []
left_index = right_index = 0
while left_index < len(left) and right_index < len(right):
if left[left_index] < right[right_index]:
result.append(left[left_index])
left_index += 1
elif left[left_index] > right[right_index]:
result.append(right[right_index])
right_index += 1
else:
# Append the remaining elements from both halves
result.extend(left[left_index:])
result.extend(right[right_index:])
return result