Welcome to my personal website. I use this space to share some of my thoughts and software that I write in my free time. Sometimes I also publish photos. If you want to get in touch please use LinkedIn or Mastodon.
Given a single linked list, sort the values in ascending order.
The solution for the single linked list looks as follows. It has a time complexity of O(n*log(n)). The technique here is first split the list in two lists of (almost) equal length. Then split the resulting lists again along the middle until the list contains only 1 or 0 elements.
This leaves only at most 2 elements to compare. If the left one is less than the right one, attach the left one to right.next and vice versa. This small list is now sorted. When going up the stack, the left and right lists are therefore sorted as well and can be merged in a similar fashion. This ultimately results in a completely sorted list.
Runtime: 1282 ms, faster than 22.47% of Python3 online submissions for Sort List. Memory Usage: 86.7 MB, less than 5.62% of Python3 online submissions for Sort List.
Another option is a merge sort for a standard list in Python:
About the author
Friedrich Ewald is an experienced Software Engineer with a Master's degree in Computer Science. He started this website in late 2015, mostly as a digital business card. He is interested in Go, Python, Ruby, SQL- and NoSQL-databases, machine learning and AI and is experienced in building scalable, distributed systems and micro-services at multiple larger and smaller companies.