eniallator

Merge sort pretty printing

Jan 10th, 2018
277
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
Python 1.63 KB | None | 0 0
  1. import math
  2.  
  3. def merge_sort(unsorted, max_iterations=None, level=1):
  4.     """Performs a merge sort on an input list of numbers/characters"""
  5.     curr_entry = [[0, unsorted]] if not max_iterations else []
  6.     max_iterations = max_iterations or math.ceil(math.log2(len(unsorted))) * 2
  7.  
  8.     mid = len(unsorted) // 2
  9.     old_left = unsorted[:mid]
  10.     old_right = unsorted[mid:]
  11.  
  12.     left_progress = merge_sort(old_left, max_iterations, level + 1) if len(old_left) > 1 else [old_left, []]
  13.     right_progress = merge_sort(old_right, max_iterations, level + 1) if len(old_right) > 1 else [old_right, []]
  14.    
  15.     left = left_progress[0]
  16.     right = right_progress[0]
  17.  
  18.     curr_entry += [[level, old_left, old_right], [max_iterations - level, list(left), list(right)]]
  19.  
  20.     reversed_sorted = [
  21.         left.pop()
  22.         if left and (
  23.             not right
  24.             or left[len(left) - 1] > right[len(right) - 1]
  25.         ) else right.pop()
  26.         for i in range(len(unsorted))
  27.     ]
  28.  
  29.     return [reversed_sorted[::-1], left_progress[1] + right_progress[1] + curr_entry]
  30.  
  31. def pretty_print(raw_progress):
  32.     layers = []
  33.     for state in raw_progress[1]:
  34.         level = state[0]
  35.         while level >= len(layers):
  36.             layers.append([])
  37.         for data in state[1:]:
  38.             if data:
  39.                 layers[level].append(data)
  40.     layers.append([raw_progress[0]])
  41.     return '\n'.join([''.join([str(entry) for entry in level]) for level in layers])
  42.  
  43.  
  44. 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]
  45. progress = merge_sort(ran_list)
  46. print(pretty_print(progress))
Advertisement
Add Comment
Please, Sign In to add comment