introduction

There are three sort algorithms with regard to tree topology. They are:

• tree search sort
• tree select sort (alias competitors sort)
• heap sort

Tree search sort is an algorithm which gets a sorted serial by middle order traversal on a binary search tree. Each node of them has a left child (if exists) with a lesser value and a right child(if exists) with a greater value.

Tree select sort is what we talk about mainly today. This algorithm also constructs a binary tree and simulate the process on 1 versus 1 competition. The leaves of the tree is all elements wanted to be sorted. We group them in pairs, and then start a game(comparation) within the group. The value of the winner can we put into the parent node of them. Last, we can get the minimum value on the root node of the binary tree. This process wastes time about $ O(n) $. We mark the leaf node with the selected minimum value as infinite and then repeat the previous process to select the second smallest value. This process will take times about $ O(log n) $ because only the path from the marked leaf to the root will be updated. Repeat the process until all leaf values are chosen. As results, the overall time complexity is \( O(n \cdot log n) \) .

Heap sort algorithm is an improvement of tree select sort algorithm for taking up less space.

implementation details

Code is easy by python.

import math
import random
from typing import List

"""
Tree Select Sort
"""

def treeSort(nums:List[int]) -> List[int]:
    # construct a tree （ponder for a while, we will know the number of elements should be the power of 2.
    n = len(nums)
    maxInt = 1 << 62
    nums = nums + [maxInt]
    m = 2 ** int(1 + math.log2(n) + 1e-3)  # we pads the the number of elements to be m 
    tree = [n] * (2 * m)
    for i in range(n):
        tree[m + i] = i
    for i in range(len(tree) - 1, 1, -2):
        tree[i // 2] = tree[i] if nums[tree[i]] < nums[tree[i - 1]] else tree[i - 1]
    # select the minimum in turn
    sorted = []
    for i in range(n):
        minIndex = tree[1]
        sorted.append(nums[minIndex])
        # update the tree
        j = minIndex + m
        tree[j] = n
        while True:
            if(j % 2 == 0):
                tree[j // 2] = tree[j] if nums[tree[j]] < nums[tree[j + 1]] else tree[j + 1]
            else:
                tree[j // 2] = tree[j] if nums[tree[j]] < nums[tree[j - 1]] else tree[j - 1]
            j = j // 2
            if j <= 1:
                break
    return sorted

if __name__ == '__main__':
    randomList = [ random.randint(0, 100) for i in range(100)]
    print(randomList)
    sorted = (treeSort(randomList))
    randomList.sort()
    print(sorted)
    print(randomList)
    assert sorted == randomList

test results

Test results show that our implementation is correct!