0

I have to implement natural mergesort on a linked list (that's easy) but I cannot change the "next" attribute of the nodes, just interchange the values they have. I also cannot go backwards because the nodes don't have a "prev" attribute. (Linked lists don't have random access) And I can't create new nodes.

I just need some hints on how the merge function should be.

I understand that keeping the two sublists ordered until I have them merged is the key, but I can't find a way to do it.

This is the Node class. They save a generic Item and the address of the next node

private class Node {
    Item item;
    Node next;

    public String toString() {
        if (next == null) return "[" + item + "]" + "->" + "null";
        return "[" + item + "]" + "->" + next.item + ", ";
    }
}
AstroD_
  • 11
  • 2

2 Answers2

0

For inspiration, look at the STL's inplace_sort implementation. The central part of the algorithm is a clever rotation. Of course it requires a backward traversal, which you could achieve with recursion.

In the nutshell, the merge part is along the lines of

    merge (begin, mid, end)
        left_mid = middle(begin, mid)
        right_mid = lower_bound(left_mid.value, mid, end)
        pivot = rotate(left_mid, mid, right_mid)
        merge(left, left_mid, pivot)
        merge(pivot, right_mid, end)

pivot above is a node into which the initial begin landed. Bailing out of recursion is omitted for brevity.

user58697
  • 7,808
  • 1
  • 14
  • 28
  • There's a std::inplace_merge, but it uses a buffer. The in place just means the merged result will be in the same container as the input parameters. – rcgldr May 14 '19 at 03:45
  • If backwards rotation via recursion is done, that will require O(n) stack space, at which point, the code might as well use an array of pointers to nodes and sort via the array of pointers. – rcgldr May 14 '19 at 03:52
  • @rcgldr I am afraid you are mistaken. It _may_ use a buffer if available, but it is not required. The logarithmic stack space is required though. The rotation via reversal is easy to implement, but again, a classic Dijkstra rotation doesn't need extra space at all. – user58697 May 14 '19 at 04:19
  • I looked at the code in Visual Studio's implementation of std::inplace_merge, if it fails to allocate a buffer, it keeps trying at ever smaller sizes. Once it gets a buffer, it splits up the merging into smaller parts depending on the size of the buffer it eventually allocated. – rcgldr May 14 '19 at 08:28
  • Looking at [c++ std::inplace_merge](https://en.cppreference.com/w/cpp/algorithm/inplace_merge), under exceptions it states "If the algorithm fails to allocate memory, std::bad_alloc is thrown." – rcgldr May 14 '19 at 13:51
0

This requires some type of inplace sort, at which point it ceases to be a natural merge sort, at best some type of hybrid. Unless the code plans to implement swap via | A = A xor B | B = A xor B | A = A xor B |, the code will need one temporary node to implement a swap. Rotate will be an issue if a temporary node is not used.

If you need stability, a block merge sort will work, but requires a scan of the list to find unique values to use as a work area, and it's a fairly complicated algorithm, with fairly recent improvements to the algorithm, such as grailsort.

https://en.wikipedia.org/wiki/Block_sort

https://github.com/Mrrl/GrailSort

If stability is not required, a somewhat simpler recursive algorithm can be used

How to sort in-place using the merge sort algorithm?

How natural merge sort fits into this isn't clear. Normally natural merge sort is a bottom up merge that uses natural run lengths. Efficient in place merge sort algorithms need to use part of a list as a work area based on run sizes, which requires using counters while scanning a list to either determine run sizes or to set boundaries for a work area.

rcgldr
  • 27,407
  • 3
  • 36
  • 61