user
|  |
| --- |
| This page uses content from **Wikipedia**. The current wikipedia article is at Tree\_sort. The original RosettaCode article was extracted from the wikipedia article № 295989333 of 15:13, 12 June 2009 . The list of authors can be seen in the page history. As with Rosetta Code, the pre **5 June 2009** text of Wikipedia is available under the GNU FDL. (See links for details on variance) |

A **tree sort** is a sort algorithm that builds a binary search tree from the keys to be sorted, and then traverses the tree (in-order) so that the keys come out in sorted order. Its typical use is when sorting the elements of a stream from a file. Several other sorts would have to load the elements to a temporary data structure, whereas in a tree sort the act of loading the input into a data structure is sorting it.

The tree sort is considered by some to be the faster method to sort a linked list, followed by Quicksort and Mergesort:

* A Comparative Study of Linked List Sorting Algorithms by Ching-Kuang Shene

Sediment sort, bubble sort, selection sort perform very badly.

* http://www.martinbroadhurst.com/sorting-a-linked-list-by-turning-it-into-a-binary-tree.html

**Task:**  
First, construct a doubly linked list (unsorted).  
Then construct a tree in situ: use the prev and next of that list as left and right tree pointers.  
Then traverse the tree, in order, and recreate a doubly linked list, again in situ, but of course now in sorted order.
assistant
**Translation of**: Go

```
# 20231201 Raku programming solution

class BinaryTree { has ($.node, $.leftSubTree, $.rightSubTree) is rw;

   method insert($item) {
      if not $.node.defined {
         $.node = $item;
         ($.leftSubTree, $.rightSubTree)>>.&{ $_ = BinaryTree.new }
      } elsif $item cmp $.node < 0 {
         $.leftSubTree.insert($item);
      } else {
         $.rightSubTree.insert($item);
      }
   }

   method inOrder(@ll) {
      return unless $.node.defined;
      $.leftSubTree.inOrder(@ll);
      @ll.push($.node);
      $.rightSubTree.inOrder(@ll);
   }
}

sub treeSort(@ll) {
   my $searchTree = BinaryTree.new;
   for @ll -> $i { $searchTree.insert($i) }
   $searchTree.inOrder(my @ll2);
   return @ll2
}

sub printLinkedList(@ll, Str $fmt, Bool $sorted) {
   for @ll -> $i { printf "$fmt ", $i }
   $sorted ?? say() !! print "-> "
}

my @ll  = <5 3 7 9 1>;
#my @ll = [37, 88, 13, 18, 72, 77, 29, 93, 21, 97, 37, 42, 67, 22, 29, 2];
printLinkedList(@ll, "%d", False);
my @lls = treeSort(@ll);
printLinkedList(@lls, "%d", True);

my @ll2 = <d c e b a>;
#my @ll2 = <one two three four five six seven eight nine ten>;
printLinkedList(@ll2, "%s", False);
my @lls2 = treeSort(@ll2);
printLinkedList(@lls2, "%s", True);

```

You may Attempt This Online!