CODEWITHSUNDEEP
python-3.xiteratorgeneratormergesort
Max
Max

Reputation: 1903

Merge sort with help Iterators

I develop merge sort, which can use only iterator (it is a statement of the problem). Output of my function is generator.

I write merge sort function:

def merge_sort(data):
    data1, data2 = itertools.tee(data)

    counter = 0
    for i in data1:
        counter += 1

    if counter < 2:
        return data2

    middle = int(counter / 2)

    y = itertools.islice(data2, 0, middle)
    z = itertools.islice(data2, middle, counter)

    sorted_y = merge_sort(y)
    sorted_z = merge_sort(z)

    return heapq.merge(sorted_y, sorted_z)

I test my function:

def main():
    unsorted_list = [10, 3, 5, 0, 1, -5, 6, 2]

    result = merge_sort(iter(unsorted_list))

    for i in result:
        print(i)

But It does not work. I only get the number 10. Where I did the mistake?

Upvotes: 1

Views: 324

Answers (1)

Max
Max

Reputation: 1903

This is a right function:

def merge_sort(data):
    data1, data2, data3 = itertools.tee(data, 3)

    counter = 0
    for i in data1:
        counter += 1

    if counter < 2:
        return data3

    middle = int(counter / 2)

    y = itertools.islice(data2, 0, middle)
    z = itertools.islice(data3, middle, counter)

    sorted_y = merge_sort(y)
    sorted_z = merge_sort(z)

    return merge(sorted_y, sorted_z)

Upvotes: 2

Related Questions