well, Sort::Key::Natural is a general solution that doesn't make any assumption about the strings passed. For instance it doesn't have a limit on the number of groups or on the size of the numbers that can be embedded in the strings.

But if you know the data is of the format /^K-2-D-\d+\w$/ and want to create a sorter taking advantage of it, a Sort::Key based solution is still the fastest:

use Sort::Key::Multi 'ii_keysort';
...

cmpthese(-10, {
                ...
                SKMii => sub {
                    my @s = ii_keysort { /(\d+)([A-Z])/; $1, ord $2 } 
+@data
                } } );
[download]

gives me:

SN_nsort    46.9/s       --        -81%   -89%    -90%        -92%    
+ -96%  -96%
SKN_natsort  244/s     420%          --   -43%    -47%        -58%    
+ -79%  -81%
ST_sub       427/s     812%         75%     --     -7%        -27%    
+ -62%  -66%
GRT_sub      460/s     881%         89%     8%      --        -22%    
+ -60%  -64%
GRT_sprintf  587/s    1152%        141%    37%     28%          --    
+ -48%  -54%
GRT_pack    1136/s    2323%        366%   166%    147%         94%    
+   --  -11%
SKMii       1272/s    2614%        422%   198%    177%        117%    
+  12%    --
[download]