Sunday, January 19, 2014

Insertion sort on linked list

If you want a simpler algorithm that needs only O(1) space, you can also consider using insertion sort to sort the linked lists. While insertion sort is easier to implement, it runs in O(n2) time in the worst case (though it also has O(n) best-case behavior), so it's probably not a good choice unless you specifically want to avoid merge sort.
The idea behind the insertion sort algorithm is as follows:
  1. Initialize an empty linked list holding the result.
  2. For each of the three linked lists:
    1. While that linked list isn't empty:
      1. Scan across the result list to find the location where the first element of this linked list belongs.
      2. Insert the element at that location.



Post a Comment