It is a sorting algorithm that uses hash function f in Python for data science with the property of order-preserving function, which states in case x<= y, then f(x) <= f(y).
The algorithm uses address table for storing the values which is simply a list of linked lists. The hash function applies to each value in array for finding its corresponding address in the address table. The values are then insert at their corresponding addresses in a sort manner by comparing them to values already present at that address.
The figure given below is a representation of the address table for the examples we have discussed.
Here we iterate through each address one by one and then inserts the values at that address in the input array.
The implementation of the above approach is as follows.
The time complexity of the algorithm is O(n) in the best case scenario. It happens when the values in an array are uniformly distributed within a specific range.
The worst case time complexity which we can have is O(n²). It will occur when most of the values occupy 1 or 2 addresses because significant work is require for inserting each value at its proper place.