insertion-sort

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: [Read More]

Merge sort is the best choice. At a first appearance, merge sort may be a good selection since the middle element is required to subdivide the given list into 2 halves, but we can easily solve this problem by moving the nodes alternatively to 2 lists. It is reasonable to expect that you cannot do any better than O(N log N) in running time, whenever we use comparison based sorts. [Read More]

The sorting problem Input: Array of numbers , unsorted. Eg. Output : Same numbers sorted in some order, say increasing order. Eg. Insertion sort: An efficient elementary sort method which places each element in it’s proper place among the elements which are already placed Pseudocode for selection sort Starts by considering the first two elements of the array data, if out of order, swap them  Consider the third element, insert it into the proper position among the first three elements. [Read More]

A comparison sort is a type of sorting algorithm that only reads the list elements through a single abstract comparison operation (often a “less than or equal to” operator) that determines which of two elements should occur first in the final sorted list. The only requirement is that the operator obey two of the properties of a total order: if a ≤ b and b ≤ c then a ≤ c (transitivity) for all a and b, either a ≤ b or b ≤ a (totalness or trichotomy). [Read More]