Merge sort looks like a best choice for sorting the linked list.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.

We have discussed the sorting options for linked list

Another O(n log n) sort that you can implement on linked lists is a modification of quicksort. Although the linked list version of quicksort is fast (still O(n log n) expected), it isn't nearly as fast as the in-place version that works on arrays due to the lack of locality effects from array elements being stored contiguously. However, it's a very beautiful algorithm as applied to lists.

The intuition behind quicksort is as follows:

The one challenge in getting this working is picking a good pivot element. It's well known that quicksort can degenerate to O(n

We have discussed the sorting options for linked list

**here**. Here we will discuss about quick sort.Another O(n log n) sort that you can implement on linked lists is a modification of quicksort. Although the linked list version of quicksort is fast (still O(n log n) expected), it isn't nearly as fast as the in-place version that works on arrays due to the lack of locality effects from array elements being stored contiguously. However, it's a very beautiful algorithm as applied to lists.

The intuition behind quicksort is as follows:

- If you have a zero- or one-element list, the list is sorted.
- Otherwise:
- Choose some element of the list to use as a pivot, say first element.
- Split the list into three groups - elements less than the pivot, elements equal to the pivot, and elements greater than the pivot.
- Recursively sort the smaller and greater elements.
- Concatenate the three lists as smaller, then equal, then greater to get back the overall sorted list.

The one challenge in getting this working is picking a good pivot element. It's well known that quicksort can degenerate to O(n

^{2}) time if the choice of pivot is bad, but it is also known that if you pick a pivot element at random the runtime is O(n log n) with high probability. In an array this is easy (just pick a random array index), but in the linked list case is trickier. The easiest way to do this is to pick a random number between 0 and the length of the list, then choose that element of the list in O(n) time. Alternatively, there are some pretty cool methods for picking an element at random out of a linked list; one such algorithm is described here.
## 0 comments:

## Post a Comment