*Applied Discrete Structures *by Alan Doerr & Kenneth Levasseur is licensed under a Creative Commons Attribution - Noncommercial - No Derivative Works 3.0 United States License.

For more information on the algorithm, see Section 10.4 of Applied Discrete Structures. This is really all Python, although it's evaluated in Sage.

We implement the binary tree sort algorthm in SageMath by first defining a

`Node`

in the the tree to contain three components, a key value, a left child and a right child. This is accomplished with the following code. An expression of the form `Node(k)`

creates a node with key `k`

and no children.We define the function

`insert_sort`

to recursively insert a key value, `b`

, into a tree rooted at `r`

. We will use this function to build a binary tree. Smaller key values are steered to the left and larger ones to the right.Once the tree is built, we traverse it with the function

`inorder_traverse`

, which assembles a sorted list.We demonstrate the process with a list of integers.

The first number in the list is placed at the root of our tree and then the rest are inserted using

`insert_sort`

. Note: In Python (and hence in SageMath), all but the first entry in a list `a`

is most easily specified using slicenotation,

`a[1:]`

.Now we traverse the tree to get our sorted list.

[811, 1884, 1943, 2324, 2923, 2945, 2993, 3390, 4263, 4545, 5306, 6461, 6810, 6953, 7082, 7333, 7909, 8229, 8260, 8337, 8414, 8663, 8945, 9352, 9656]