Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- import math
- def merge_sort(unsorted, max_iterations=None, level=1):
- """Performs a merge sort on an input list of numbers/characters"""
- curr_entry = [[0, unsorted]] if not max_iterations else []
- max_iterations = max_iterations or math.ceil(math.log2(len(unsorted))) * 2
- mid = len(unsorted) // 2
- old_left = unsorted[:mid]
- old_right = unsorted[mid:]
- left_progress = merge_sort(old_left, max_iterations, level + 1) if len(old_left) > 1 else [old_left, []]
- right_progress = merge_sort(old_right, max_iterations, level + 1) if len(old_right) > 1 else [old_right, []]
- left = left_progress[0]
- right = right_progress[0]
- curr_entry += [[level, old_left, old_right], [max_iterations - level, list(left), list(right)]]
- reversed_sorted = [
- left.pop()
- if left and (
- not right
- or left[len(left) - 1] > right[len(right) - 1]
- ) else right.pop()
- for i in range(len(unsorted))
- ]
- return [reversed_sorted[::-1], left_progress[1] + right_progress[1] + curr_entry]
- def pretty_print(raw_progress):
- layers = []
- for state in raw_progress[1]:
- level = state[0]
- while level >= len(layers):
- layers.append([])
- for data in state[1:]:
- if data:
- layers[level].append(data)
- layers.append([raw_progress[0]])
- return '\n'.join([''.join([str(entry) for entry in level]) for level in layers])
- ran_list = [23,5,6,8,812,4,124,3,7,1,12,5,85,0,24,87,34,242,213,566,21,7,2143,635,573,243,548,89,456]
- progress = merge_sort(ran_list)
- print(pretty_print(progress))
Advertisement
Add Comment
Please, Sign In to add comment