Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It only takes a minute to sign up.
Sign up to join this community
Are there any known / efficient dynamic programming solutions to sorting?
I understand of course that dynamic programming applies to scenarios where we have overlapping subproblems and optimal substructure, but I wonder if there are transformations and representations of the sorting problem where these conditions are met, and even better, where doing so may actually be useful.
Dynamic programming is an algorithmic technique, algorithms are classified as dynamic programming according to what their high-level structure "looks like", not according to a formal definition. If you really wanted to, you could force some sorting algorithms to fit into the dynamic-programming paradigm.
Let $A[1:n]$ be the array to sort, assume for simplicity that all its elements are distinct, and define $OPT[i]$ as the sorted array containing the smallest $i$ elements of $A$.
According to this definition $OPT[0]$ is the empty array and, if you solve the subproblems in increasing order of $i$, you can recombine them as follows:
$$\displaystyle \forall i=1,\dots,n \quad\quad OPT[i] = OPT[i-1] \circ \min_{x \in A \setminus OPT[i-1]} x,$$
where $\circ$ denotes concatenation. The optimal solution is in $OPT[n]$. Computing any $OPT[i]$ requires $O(n)$ time, therefore the total time needed is $O(n^2)$. At any point in time, you only need to store one $OPT[i]$, so the space complexity is $O(n)$.
This is essentially an ugly way to describe selection sort.
You can always reduce sorting to another problem. Moreover, sorting is in P, so it can be reduced in polynomial time to any other problem in P. There are countless problems that can be solved via dynamic programming in P, so the answer is yes.
