Poolsort

Poolsort (method) is a comparison-based sorting algorithm, and is part of the selection sort family. Poolsort was designed by Alex Westphal.

Overview

The pool sort works as its name suggests. It begins by building a set of pools out of the data set then finding the smallest item in each pool using a selection. These are then put into a master pool. The next largest item is always found with a selection on the master pool. The item is subsequently replaced in the master pool by re-performing the selection on only the source child pool.

Poolsort improves upon the standard selection sort in that it only does a selection from the master pool and one child pool on each pass instead of the entire data set.

Use

Poolsort has no practical use in computing as it is much more complex in both time and space than other algorithms such as quicksort and mergesort.

It is practical for use in sorting by groups of people because its conceptually simple and the number of pools can be varied to accommodate different numbers of people.

Optimisation

The optimal size of each pool as well as the number of pools is $\sqrt{n}$. This is because the number of comparisons for each pass is p + s where p and s represent the number of pools and the size of the pools respectively as well as satisfying the equation n = p * s.

When Poolsort is performed with people or multiple devices the size of individual pools can be set depending on the capacity of an individual person or device.

Performance

The worst case number of comparisons is calculated as follows:

First Item:

 N₁ = p * (s−1) + p
 N₁ = p * s
 $N_1 = O(\sqrt{n}) * O(\sqrt{n})$
 N₁ = O(n)

Subsequent Item:

 N_i = p + s
 $N_i = O(\sqrt{n}) + O(\sqrt{n})$
 $N_i = O(\sqrt{n})$

Total:

 N = N₁ + (N₂+N₃+...+N_n)
 $N = O(n) + O(n)*O(\sqrt{n})$
 $N = O(n\sqrt{n})$
 

Implementation

Implementation in Scala:

def poolSort[T](array: Array[T]): Array[T] = {

   val newArray = new Array[T](array length)

Check for empty array

   if((array length) == 0) {
     return newArray
   }

Calculate Pool size

   val size = (Math sqrt (array length)) + 1

Create Pools

   var numPools = if((array length) > ((size-1)*size)) { size } else { size-1 }
   val pools = new Array[Pool](numPools)
   for(i <- 0 until (numPools - 1) ) {
     pools(i) = new Pool(array, (i*size), size)
     pools(i).findMax()
   }
   pools(numPools-1) = new Pool(array, ((numPools-1)*size), ((array length)-((numPools-1)*size)))

Run Selection

   var maxPos = 0
   for(j <- 0 until array.length) {
     maxPos = 0
     for(i <- 1 until numPools) {
       if(pools(i).getMax < pools(maxPos).getMax) {
         maxPos = i
       }
     }
     newArray(j) = pools(maxPos).getMax
     if(pools(maxPos) isEmpty) {
       numPools -= 1
       pools(maxPos) = pools(numPools)
     } else {
       pools(maxPos) findMax
     }
   }
   newArray

}

Pool Class

class Pool(array: Array[Int], left: Int, size: Int) {

 var right = left+size

Pool Max Function

 def getMax = array(right)

Pool Empty Check Function

 def isEmpty = (left==right)

Find Pool Max Function

 def findMax() = {
   var maxPos = left
   for(i <- (left+1) until right) {
     if(array(i) < array(maxPos)) {
       maxPos = i
     }
   }
   right -= 1
   val temp = array(maxPos)
   array(maxPos) = array(right)
   array(right) = temp
 }

}