Question

Change mergesort so that the algorithm removes duplicate items in the list as well as sorts the remaining items. For example, on input (15, 2, 21, 5, 15, 2, 15), the output should be (2, 5, 15, 21).

Answer 1

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