Generally, we can implement algorithms in-place and out-of-place.

However, I can't say for certain that radix sort can be implemented in both ways.

  • 1
    $\begingroup$ What prevents you from checking that? $\endgroup$ – Dmitry Apr 15 at 0:35
  • $\begingroup$ @Dmitry well, it does not return a new array, but it does stores some variables. So I got my answer, 'it depends' (see Nathaniel's answer below) $\endgroup$ – Monther Apr 15 at 2:21
  • $\begingroup$ Analyzing a piece of Python code is out-of-scope for this site. Coding and implementation-specific questions are off-topic here. $\endgroup$ – D.W. Apr 15 at 6:28
  • $\begingroup$ @D.W. See my edit. $\endgroup$ – Monther Apr 15 at 22:24
  • 1
    $\begingroup$ You should check en.wikipedia.org/wiki/… $\endgroup$ – Nathaniel Apr 15 at 22:42

It depends on the definition of in-place algorithm you are using.

  • if in-place just means that the algorithm transforms the input without returning a new array, then yes;
  • if you also want to use no additionnal data structure, or limit the additionnal space usage to be $o(n)$, then no, because of the creation of the arrays count and output.

There are different meanings to an in-place algorithm, as stated here.

  • $\begingroup$ can we implement radix sorting algorithm without using additional space? $\endgroup$ – Monther Apr 15 at 2:07
  • 2
    $\begingroup$ Not to my knowledge. $\endgroup$ – Nathaniel Apr 15 at 2:13

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.