I was wondering if Radix sort can clearly be defined as being a divide-and-conquer algorithm.
As I understand a divide and conquer algorithm is defined by:
A divide-and-conquer algorithm recursively breaks down a problem into two or more sub-problems of the same or related type, until these become simple enough to be solved directly. The solutions to the sub-problems are then combined to give a solution to the original problem. wikipedia devide-and-conquer algorithm
Lets assume we just use numbers from 0 to 999 for simplification. As far as I understand in this case I first split my problem into 3 buckets, where each bucket is assigned to least significant digit, the middle one and the most significant digit.
Next I have to sort each bucket (starting with the least significant digit and working to the most significant) with for e.g. counting sort.
I think that breaking down the problem is satisfied, so should in my opinion be the solving of this problem (sorting using counting sort in O(n), as this is already the most simple solution) but I am not sure about the combining step.
My question now is: Is the definition of divide-and-conquer satisfied? Did I even use the correct definition? If not what did I do wrong in my thought process?
What I already did:
I already tried looking for some explicit statements that radix sort is a divide-and-conquer algorithm, but didn't find the answer. Neither is it explicitly written on wikipedia, nor do some related questions provide the answer. I also researched in my Algorithms and Datastructures book (Algorithmen und Datenstrukturen) but it didn't explicitly state that.
The closest call was this post Why does radix sort divides it's elements though it is not a Stable Sort?:
First, Radix-sort divide and group because it works on divide and conquer technique.
It says that radix sort uses the divide-and-conquer technique but does not explicitly state that is is itself a divide-and-conquer algorithm.
no, it is not. radix sort in base 10, say, of numbers up to 10^N in magnitude, just does the full sweep through the whole list one time after another, N times, each time using 10 buckets. thus it is a genuinely iterative algorithm. you could code this loop up as a recursion, but that recursion is not related to the nature of the problem, just to the superficial way of coding up the solution. IOW it'd be recursion related to counting from 1 to N, not to the radix sort itself.
that is to say, there's no reduction in problem size at all, from one pass over the list to the other. the problem size stays the same. what is reduced is the "entropy" in the list, as if by "side effect". but we are not searching in the entropy space, nor are we subdividing it.