To implement a sorting algorithm to sort an array in O(N) running time complexity we can use Radix sort. The details for the algorithm is given below.

Radix Sort

Properties

• It is very efficient because there is no comparison
• With the help of this algo we can sort array in O(n) running time complexity
• Running Time: O(n*m) where m is the maximum no of digits in an array
• It is a stable sorting algorithm
  
  We can implement this algorithm in two different ways

Least Significant string sorting

• We sort the array from the least significant digit from right to left
• It can be used for fixed length string or fixed-length numbers
• Start sorting character from left and sort them independently
• Most common interview question

Most significant digit string sort

• Most significant digit from left to right
• It has several advantages
• can be sublinear in input
• examines just enough character to sort

Implementation in Python

ITEMS_IN_BUCKET = 10 # No of digits
class RadixSort:
    """Implementation of radix sort"""
    def __init__(self,data):
        # Initialize radix sort
        self.data = data
    
    def get_digits(self):
        # Get No of digits
        return len(str(max(self.data)))
    
    def sort(self):
        # Function to sort the array
        for digit in range(self.get_digits()):
            self.counting_sort(digit)
    def counting_sort(self,d):
        count_array = [[] for _ in range(ITEMS_IN_BUCKET)]
        
        # store the count of each element in count array O(N)
        
        for num in self.data:
            # Calculate the index of the given bucket
            index = (num // (10 ** d)) % 10
            count_array[index].append(num)
        # We have to consider all the items in count array(list)
        z = 0
        for i in range(len(count_array)):
            while len(count_array[i]) > 0:
                # it takes O (N) linear time complexity - dictionary O(1)
                self.data[z] = count_array[i].pop(0)
                z = z + 1
            
    

n = [5,3,13,900,15,19,58,98]
radix_sort = RadixSort(n)
radix_sort.sort()
radix_sort.data
[3, 5, 13, 15, 19, 58, 98, 900]