fork download
copy 
  1. #!python
  2. import random
  3.  
  4. class llist:
  5. 	#inits the new linked list node with data
  6. 	def __init__(self, data):
  7. 		self.data = data
  8. 		self.next = None
  9. 	#links a new node to the current one (destructive if one exists already)
  10. 	def append(self, node):
  11. 		self.next = node
  12. 		return self.next
  13. 	#works out the length of the list from current node
  14. 	def length(self):
  15. 		length = 1
  16. 		node = self
  17. 		while node.next:
  18. 			node = node.next
  19. 			length += 1
  20. 		return length
  21. 	#cut the current list after 'length' nodes, return the cut off list
  22. 	def cut(self,length):
  23. 		node = self
  24. 		while length > 1 and node.next:
  25. 			node = node.next
  26. 			length -= 1
  27. 		next = node.next
  28. 		node.next = None
  29. 		return next
  30. 	#compare with another list, return both lists as a tuple, ordered by data in the head nodes of each
  31. 	def order(self, other):
  32. 		if not other: return (self, None)
  33. 		return (self, other) if other.data > self.data else (other, self)
  34. 	#print list data
  35. 	def print_list(self, prepend = ''):
  36. 		node = self
  37. 		while node:
  38. 			print (prepend + str(node.data))
  39. 			node = node.next
  40.  
  41. def mergesort(unsorted):
  42.   #dummy start node
  43. 	start = llist(None)
  44. 	start.append(unsorted)
  45. 	list_length = unsorted.length()
  46. 	sublist_length = 1
  47. 	while sublist_length < list_length:
  48. 		last  = start
  49. 		sub_a = start.next
  50. 		while sub_a:
  51. 			sub_b = sub_a.cut(sublist_length)
  52. 			end   = sub_b.cut(sublist_length) if sub_b else None
  53. 			while sub_a:
  54. 				sub_a, sub_b = sub_a.order(sub_b)
  55. 				node = sub_a
  56. 				sub_a = sub_a.cut(1)
  57. 				last = last.append(node)
  58. 				if not sub_a:
  59. 				  sub_a, sub_b = sub_b, None
  60. 			sub_a = end
  61. 		sublist_length *=2
  62. 	return start.next
  63.  
  64. #create a list with a length that doesn't match 2^n to show that it handles it fine
  65. #create a dummy node to begin the list
  66. start = llist(None)
  67. end = start
  68. for i in range(16):
  69. 	end = end.append(llist(random.randint(0, 50)))
  70. unsorted = start.next
  71. print ('unsorted:')
  72. unsorted.print_list()
  73. sorted = mergesort(unsorted)
  74. print('sorted:')
  75. sorted.print_list()
Success #stdin #stdout 0.02s 37088KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
unsorted:
15
25
5
6
15
6
4
49
10
18
15
1
22
33
10
35
sorted:
1
4
5
6
6
10
10
15
15
15
18
22
25
33
35
49
https://ideone.com/r39lvU
language:
Python 3 (python  3.12)
created:
8 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!