# Sorting with gaps

Suppose we have a directory containing $N$ files whose names are numerals, but not necessarily contiguous numerals. Let's say for concreteness that each file contains an email message, each of which has a date, and we would like to rename the files so that the order of the filenames is the same as the order of the dates. Letting $A\prec B$ mean that the date in the file named $A$ is earlier than the date in the file named $B$, we want $$A<B \text{ if and only if } \def\date{\operatorname{date}}A \prec B.\tag{*}$$

I want to do this with as few file-rename operations as possible.

I can do this by sorting the filenames in memory and then applying the permutation that is computed by the sort. The question is how to optimally effect the required permutation.

The following algorithm requires $N$ rename operations:

Suppose the permutation is $P$. Let $c$ be some number larger than the largest filename, and rename each file $i$ to $c+P(i)$.

But this may not be optimal. For example, suppose the files are named $2,3,5$, where file $5$ contains the earliest email message and $3$ contains the latest. We have $5\prec 2\prec 3$. Sorting will tell us that we need to apply the permutation $2\to 3\to 5\to 2$. The method above performs the following 3 renames (taking $c=10$):

1. $2\to 13$
2. $3\to 15$
3. $5\to 12$

But we can do better; for this example it suffices to perform the single rename $5\to 1$.

What is an algorithm which, given the filenames and the required permutation, efficiently computes an optimal renaming?

It may be helpful to think of this as sorting an array $A$, where some of the elements are null, and can be disregarded. After sorting, the contents of the array must be the same. But whereas with ordinary sorting, we want $A[i]\prec A[j]$ for all $i<j$, here we only require that that condition hold when $A[i]$ and $A[j]$ are non-null.

[Thanks to David Richerby for suggesting a major revision of the question.]

• My first thought is that calculating the LCSS between the sorted file sequence and the integers (you only need to consider the range $[\min S - |S|,\max S + |S|]$) gives you the files which are already in the correct position. The two things that complicate things are whether or not you allow negative numbers, and whether or not the gaps in the LCSS are large enough to accommodate files which aren't in the correct position. – Pseudonym Aug 19 '14 at 3:51
• FWIW, one does not have to blow up the file names. If the permutation has cycles of lengths $l_1, \dots, l_k$ we can get the same filenames (in the correct order) with $\sum (l_i + 1) = n + k$ renamings by using a temporary name. Anyway, practical question: would you not want to introduce a name scheme that leaves sizable gaps? Then you'd do a full renaming in iteration one, and then many updates could happen fast (cf. e.g. @Pseudonym). Are we allowed to amortize in this way? – Raphael Oct 13 '15 at 15:31
• Practical question 2: are the renaming operations themselves actually a bottleneck? They are not asymptotically dominant and only happen in the file index. – Raphael Oct 13 '15 at 15:33
• The renaming operations are themselves actually a bottleneck in practice. – Mark Dominus Oct 13 '15 at 15:51