Merge sort without recursion

Hello, I’ve learnt Merge sort using recursion by python. And I want to write Merge sort without recursion but I get error at line 21: TypeError: ‘set’ object is not subsciptable.

def merge(left, right):
  result = []

  while (left and right):
    if left[0] < right[0]:
      result.append(left[0])
      left.pop(0)
    else:
      result.append(right[0])
      right.pop(0)

  if left:
    result += left
  if right:
    result += right

  return result
def its_magic(list,k):
    result = []
    while len(list)>=2*k:
        result += merge(list[0:k],list[k:2*k])
        if len(list) == 2*k:
            list = []
        else:
            list = list[2*k:]
    if not list:
        return result
    elif len(list) < k:
        result += list
        return result
    return result + merge(list[0:k],list[k:])
def merge_sort(list):
    i = 1
    result = []
    while i<len(list):
        result = its_magic(list,i)
        i*=2
    return result
a = {5,2,4,5,613,43,534,53,12,4,6,88}
print(merge_sort(a))

well… do you agree? where do you have a set and where do you use subscripting? what is a set what is subscripting?

you also have a line number, allowing you to look at what you have there and what you do with those things


unrelated:

this operation is as much work as copying a whole list. lists do not support removals or additions at the front, as such this will instead move everything and make the addition or removal at the end. maybe you meant to use a different data structure, or maybe you did not actually mean to modify the sources and could instead iterate through them

similar deal in its_magic where you repeatedly copy the rest of the list – what you could do instead is to create chunks of k size, and merge each pair. you could also use an offset and change the offset instead of copying the list

numpy arrays is an option as well, their slicing does not copy, instead creates a view, making their slicing O(1) instead of list’s O(N) – so you could pop 0 by slicing arr[1:] or drop x elements from the front with arr[x:]

This topic was automatically closed 41 days after the last reply. New replies are no longer allowed.