https://www.chiark.greenend.org.uk/~sgtatham/algorithms/listsort.html

Question

To sort a linked list when I already have a linked list of n elements do we need any auxiliary array or not? Please refer to the article- https://www.chiark.greenend.org.uk/~sgtatham/algorithms/listsort.html

Answer 1

You dont need necessarily require an auxilary array for sorting. This is a pseudo code for bubble sort:

function bubbleSort(head):
    if head is null:
        return

    swapped = true
    lptr = null

    while swapped is true:
        swapped = false
        ptr1 = head

        while ptr1.next is not lptr:
            if ptr1.data > ptr1.next.data:
                swap(ptr1.data, ptr1.next.data)
                swapped = true
            ptr1 = ptr1.next

        lptr = ptr1

 

This is what I saw in wikipedia regarding merge sort:

Merge sort is often the best choice for sorting a linked list: in this situation it is relatively easy to implement a merge sort in such a way that it requires only Θ(1) extra space, and the slow random-access performance of a linked list makes some other algorithms (such as quicksort) perform poorly, and others (such as heapsort) completely impossible.