@@ -74,6 +74,86 @@ def _msd_radix_sort(list_of_ints: List[int], bit_position: int) -> List[int]:
7474 return res
7575
7676
77+ def msd_radix_sort_inplace (list_of_ints : List [int ]):
78+ """
79+ Inplace implementation of the MSD radix sort algorithm.
80+ Sorts based on the binary representation of the integers.
81+ >>> lst = [1, 345, 23, 89, 0, 3]
82+ >>> msd_radix_sort_inplace(lst)
83+ >>> lst == sorted(lst)
84+ True
85+ >>> lst = [1, 43, 0, 0, 0, 24, 3, 3]
86+ >>> msd_radix_sort_inplace(lst)
87+ >>> lst == sorted(lst)
88+ True
89+ >>> lst = []
90+ >>> msd_radix_sort_inplace(lst)
91+ >>> lst == []
92+ True
93+ >>> lst = [-1, 34, 23, 4, -42]
94+ >>> msd_radix_sort_inplace(lst)
95+ Traceback (most recent call last):
96+ ...
97+ ValueError: All numbers must be positive
98+ """
99+
100+ length = len (list_of_ints )
101+ if not list_of_ints or length == 1 :
102+ return
103+
104+ if min (list_of_ints ) < 0 :
105+ raise ValueError ("All numbers must be positive" )
106+
107+ most_bits = max (len (bin (x )[2 :]) for x in list_of_ints )
108+ _msd_radix_sort_inplace (list_of_ints , most_bits , 0 , length )
109+
110+
111+ def _msd_radix_sort_inplace (
112+ list_of_ints : List [int ], bit_position : int , begin_index : int , end_index : int
113+ ):
114+ """
115+ Sort the given list based on the bit at bit_position. Numbers with a
116+ 0 at that position will be at the start of the list, numbers with a
117+ 1 at the end.
118+ >>> lst = [45, 2, 32, 24, 534, 2932]
119+ >>> _msd_radix_sort_inplace(lst, 1, 0, 3)
120+ >>> lst == [32, 2, 45, 24, 534, 2932]
121+ True
122+ >>> lst = [0, 2, 1, 3, 12, 10, 4, 90, 54, 2323, 756]
123+ >>> _msd_radix_sort_inplace(lst, 2, 4, 7)
124+ >>> lst == [0, 2, 1, 3, 12, 4, 10, 90, 54, 2323, 756]
125+ True
126+ """
127+ if bit_position == 0 or end_index - begin_index <= 1 :
128+ return
129+
130+ bit_position -= 1
131+
132+ i = begin_index
133+ j = end_index - 1
134+ while i <= j :
135+ changed = False
136+ if not ((list_of_ints [i ] >> bit_position ) & 1 ):
137+ # found zero at the beginning
138+ i += 1
139+ changed = True
140+ if (list_of_ints [j ] >> bit_position ) & 1 :
141+ # found one at the end
142+ j -= 1
143+ changed = True
144+
145+ if changed :
146+ continue
147+
148+ list_of_ints [i ], list_of_ints [j ] = list_of_ints [j ], list_of_ints [i ]
149+ j -= 1
150+ if not j == i :
151+ i += 1
152+
153+ _msd_radix_sort_inplace (list_of_ints , bit_position , begin_index , i )
154+ _msd_radix_sort_inplace (list_of_ints , bit_position , i , end_index )
155+
156+
77157if __name__ == "__main__" :
78158 import doctest
79159
0 commit comments