First assemble all the file names, then sort and print:

use strict;
use 5.01;
use File::Find;
my $dir = "lib";
File::Find::find (\&search, $dir);

my @files;
sub search {
    push @files, $_ if -f;
}
say for sort { lc($a) cmp lc($b) } @files;
[download]

Or if you want a per-directory view,

my @files;
sub search {
  push @files, $_ if -f;
}

sub handle_directory {
  @files = sort { lc($a) cmp lc($b) } @files;
  # do something with @files
  print "@files\n";

  # get ready for the next directory
  undef @files;
}

File::Find::find( {
  wanted      => \&search,
  bydepth     => 1,
  postprocess => \&handle_directory
}, $directory );
[download]

Why not put your file names into a list rather than printing them out, and then sorting the list ?

So, something like this , untested :)

use strict;
use File::Find;
my @files;

my $dir = "/some/dir/in/linux";
File::Find::find (\&search, $dir);

sub search {
    if (-f $_) {
       push @files,$_; 
    }
}


for (sort { your sort criteria here} @files) {
   say $_;
}
[download]

BTW I find it easier to use File::Find::Rule

my @files = File::Find::Rule->files()->in($dir);
[download]

Why not use File::Find::find's preprocess option? Something along the lines of

File::Find::find({preprocess=>sub { 
                      return sort {uc $a cmp uc $b} @_ 
                       }, 
                  wanted=>sub {
                      return if (-d);
                      say $_;
                       }
                 },@ARGV);

[download]

File::Find::Rule provides a nice front end for File::Find:

use strict;
use warnings;
use File::Find::Rule;

my $dir = ".";

my @files = File::Find::Rule->file()->in($dir);

print "$_\n" for sort { lc $a cmp lc $b } @files;
[download]

Partial output:

.project
10B.xml
10b.xml
1354903584-3827.xlsx
5a.xml
67.xml
6adh.pdb
arrays.pl
atom.pdb
Bio_SeqIO.pl
...
[download]

You may also be interested in using Sort::Naturally for a lexical sort:

use strict;
use warnings;
use File::Find::Rule;
use Sort::Naturally;

my $dir = ".";

my @files = File::Find::Rule->file()->in( $dir );

print "$_\n" for nsort @files;
[download]

Partial output

5a.xml
6adh.pdb
10b.xml
10B.xml
67.xml
1354903584-3827.xlsx
arrays.pl
atom.pdb
Bio_SeqIO.pl
Book1.xls
[download]