<p>One interesting angle on this question is the idea of using "combinatorial block designs". We want each of our sorts to give us as much information as possible, so we don't want the same pair of elements in two different sorts. That is actually achievable: we can use a combinatorial structure called a "balanced incomplete block design" (BIBD). We are looking for a (25,5,1)-BIBD, meaning there are 25 elements (25), blocked by five at a time (5), such that each pair of elements appears in exactly one block (1).</p>

<p>Such block designs have been extensively explored. It turns out that there is a (25,5,1)-BIBD. An explicit construction is given in, e.g., <a href="http://arxiv.org/ftp/arxiv/papers/0909/0909.3533.pdf" rel="nofollow">http://arxiv.org/ftp/arxiv/papers/0909/0909.3533.pdf</a> page 8.</p>

<pre><code>{(1,2,3,4,5) (6,7,8,9,10) (11,12,13,14,15) (16,17,18,19,20) (21,22,23,24,25)
(1,6,11,16,21) (2,7,12,17,21) (3,8,13,18,21) (4,9,14,19,21) (5,10,15,20,21)
(2,8,14,20,22) (3,10,11,19,22) (5,9,12,16,22) (1,7,15,18,22) (4,6,13,17,22)
(3,9,15,17,23) (5,6,14,18,23) (4,7,11,20,23) (2,10,13,16,23) (1,8,12,19,23)
(4,10,12,18,24) (1,9,13,20,24) (2,6,15,19,24) (5,8,11,17,24) (3,7,14,16,24)
(5,7,13,19,25) (4,8,15,16,25) (1,10,14,17,25) (3,6,12,20,25) (2,9,11,18,25)}
</code></pre>

<p><a href="http://www.sagemath.org/" rel="nofollow">Sage</a> can also be used to construct BIBDs.</p>

<p>That block design has 30 blocks, so it's far from optimal for this problem. But perhaps it can be combined with transitivity to devise a faster algorithm for the problem.</p>

<p><strong>Update</strong></p>

<p>It turns out that my suggestion is not much use in this problem, except to place an upper bound on the number of steps in a solution (30, the size of the BIBD). To gauge its performance, I wrote some "test bed" software (see below) which gives a visual representation of  the progress of the sort. </p>

<p>I represented the state of sortedness of the data with two graphs: g, the graph of all potential relationships among the 25 items, which starts as a complete directed graph on the 25 items, and g1, the graph of all known relationships among the 25 items. g and g1 have an obvious relationship, so keeping track of two graphs is clearly redundant, but different kinds of information can be easily extracted from g and g1 which I why I keep track of them both.</p>

<p>g starts with 600 edges, each of the 25*24 directed edges between two items. We are done when g has no non-trivial (i.e., size greater than 1) strongly connected components, in which case g can be unambiguously toposorted to give the correct ordering. That occurs when there are exactly 300 edges in g. Similarly, g1 starts with no edges, and we are done when the same 300 edges appear in g1 as in g.</p>

<p>Picking 5 items and then sorting them immediately adds up to 5 + 4 + 3 + 2 + 1 = 15 new edges to g (and removes the same number of edges from g1). I say "up to" because if any of those edges are already in g, they don't get added to the count. So if we already know A -> B and nothing about relationships between any other pair in A,B,C,D,E, then sorting those five only gives 14 new edges in g.</p>

<p>On the other hand, we can often get more arrows from a sort by exploiting transitivity. If we know that B -> F, and a sort tells us that A -> B, we can deduce that A -> F, which is an extra arrow in g. The set of all additional arrows found through transitivity can be obtained by finding the "transitive closure" of g with the new arrows added as a result of the sort. The corresponding effect on g1 can be easily found.</p>

<p>In my software below, I give an image of the graph g1, which starts out as 600 directed edges pictured as 300 blue edges with arrows on each end. Each sorting step followed by transitive closure will replace some doubled-sided blue arrows with single-sided yellow arrows. We know we're finished when all the blue arrows are gone; equivalently, when g1 has no non-trivial strongly connected components.</p>

<p>In the software below, I chose the 5 items to be sorted by picking a random unused block from the BIBD I gave earlier, then marked the block as used. It generally takes all 30 blocks to sort the 25 items in this manner. As you can see from the visualization, the process starts out well enough, but misses obvious speedups from steps 20 to 30. My conclusion is that the fastest solutions to this problem will have to be adaptive, picking 5 items to sort based on prior results.</p>

<p>Looking at the problem in this way has given me some new ideas that I may explore in another answer to the question. In the meantime, here are the two Java classes  for the program I used.</p>

<p>The GUI framework:</p>

<pre><code>package org.jgrapht.demo;

import java.awt.BorderLayout;
import java.awt.Button;
import java.awt.Color;
import java.awt.EventQueue;
import java.awt.Font;
import java.awt.event.ActionEvent;
import java.awt.event.ActionListener;

import javax.swing.BoxLayout;
import javax.swing.JFrame;
import javax.swing.JLabel;
import javax.swing.JPanel;
import javax.swing.UIManager;

public class FiveSort extends JFrame {

  private static final long serialVersionUID = 1L;
  private Font smallFont = new Font(Font.DIALOG, Font.PLAIN, 12);
  private Font largeFont = new Font(Font.DIALOG, Font.PLAIN, 36);
  private JLabel stepsLabel = new JLabel("0");
  private JLabel maxLabel = new JLabel("0");
  private JLabel averageLabel = new JLabel("");
  private int rounds = 0;
  private int totalSteps = 0;
  private double averageSteps = 0;
  private int maxSteps = 0;

  public static void main(String[] args) {
    EventQueue.invokeLater(new Runnable() {
      @Override
      public void run() {
        new FiveSort();
      }
    });
  }

  public FiveSort() {
    initGUI();
    setLocationRelativeTo(null);
    setTitle("Five Sort");
    setDefaultCloseOperation(JFrame.EXIT_ON_CLOSE);
    pack();
    setVisible(true);
  }

  public void initGUI() {
    try {
      // UIManager.setLookAndFeel( UIManager.getCrossPlatformLookAndFeelClassName() );
      UIManager.setLookAndFeel( UIManager.getSystemLookAndFeelClassName() );
    } catch (Exception e) {
      e.printStackTrace();
    }

    // title label
    JLabel titleLabel = new JLabel("Five Sort");
    titleLabel.setFont(largeFont);
    titleLabel.setBackground(Color.BLACK);
    titleLabel.setForeground(Color.WHITE);
    titleLabel.setOpaque(true);
    titleLabel.setHorizontalAlignment(JLabel.CENTER);
    add(titleLabel,BorderLayout.PAGE_START);

    // main panel 
    JPanel mainPanel = new JPanel();
    mainPanel.setLayout(new BoxLayout(mainPanel,BoxLayout.Y_AXIS));
    add(mainPanel);

    // graph panel
    FiveSortPanel graphPanel = new FiveSortPanel();
    mainPanel.add(graphPanel,BorderLayout.CENTER);

    // stats panel
    JPanel statsPanel = new JPanel();
    statsPanel.setBackground(Color.BLACK);
    mainPanel.add(statsPanel);

    JLabel stepsTitleLabel = new JLabel("Current Steps: ");
    stepsTitleLabel.setFont(smallFont);
    stepsTitleLabel.setForeground(Color.WHITE);
    statsPanel.add(stepsTitleLabel);
    stepsLabel.setFont(largeFont);
    stepsLabel.setForeground(Color.WHITE);
    stepsLabel.setText("" + graphPanel.getSteps());
    statsPanel.add(stepsLabel);

    JLabel maxTitleLabel = new JLabel("Max Steps: ");
    maxTitleLabel.setFont(smallFont);
    maxTitleLabel.setForeground(Color.WHITE);
    statsPanel.add(maxTitleLabel);
    maxLabel.setFont(largeFont);
    maxLabel.setForeground(Color.WHITE);
    maxLabel.setText("" + maxSteps);
    statsPanel.add(maxLabel);

    JLabel averageTitleLabel = new JLabel("Avg Steps: ");
    averageTitleLabel.setFont(smallFont);
    averageTitleLabel.setForeground(Color.WHITE);
    statsPanel.add(averageTitleLabel);
    averageLabel.setFont(largeFont);
    averageLabel.setForeground(Color.WHITE);
    averageLabel.setText("");
    statsPanel.add(averageLabel);

    // button panel
    JPanel buttonPanel = new JPanel();
    buttonPanel.setBackground(Color.BLACK);
    add(buttonPanel,BorderLayout.PAGE_END);

    Button newButton = new Button("Step");
    newButton.setFocusable(false);
    newButton.addActionListener(new ActionListener() {
      @Override
      public void actionPerformed(ActionEvent e) {
        if (!graphPanel.isComplete()) {
          graphPanel.step();
          stepsLabel.setText("" + graphPanel.getSteps());
        }
      }
    });
    buttonPanel.add(newButton);

    Button restartButton = new Button("Restart");
    restartButton.setFocusable(false);
    restartButton.addActionListener(new ActionListener() {
      @Override
      public void actionPerformed(ActionEvent e) {
        if (graphPanel.isComplete()) {
          ++rounds;
          totalSteps += graphPanel.getSteps();
          averageSteps = ((int)(totalSteps / (double)rounds * 10))/10.0; 
          maxSteps = Math.max(maxSteps, graphPanel.getSteps());
        }
        graphPanel.restart();
        stepsLabel.setText("" + graphPanel.getSteps());
        maxLabel.setText("" + maxSteps);
        averageLabel.setText("" + averageSteps);
      }
    });
    buttonPanel.add(restartButton);
  }

}
</code></pre>

<p>The graph manipulation routines (which require jgrapht-ext-0.9.1-uber.jar, freely available from the JGraphT site):</p>

<pre><code>package org.jgrapht.demo;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.HashMap;
import java.util.Comparator;
import java.util.List;
import java.util.Set;

import javax.swing.JPanel;

import org.jgrapht.DirectedGraph;
import org.jgrapht.Graphs;
import org.jgrapht.ListenableGraph;
import org.jgrapht.alg.StrongConnectivityInspector;
import org.jgrapht.alg.TransitiveClosure;
import org.jgrapht.ext.JGraphXAdapter;
import org.jgrapht.graph.DefaultEdge;
import org.jgrapht.graph.ListenableDirectedGraph;
import org.jgrapht.graph.SimpleDirectedGraph;

import com.mxgraph.layout.mxCircleLayout;
import com.mxgraph.swing.mxGraphComponent;
import com.mxgraph.util.mxConstants;

public class FiveSortPanel extends JPanel {
  private static final long serialVersionUID = 1L;
  private static final int ARRAY_SIZE = 25;
  private static final int SORT_SIZE = 5;
  private static final String ALPHABET = "ABCDEFGHIJKLMNOPQRSTUVWXYZ";
  private static final String STROKE_YELLOW = "strokeColor=#CCCC00";
  private Integer[][] BIBD = { 
    {1,2,3,4,5},     {6,7,8,9,10},    {11,12,13,14,15}, {16,17,18,19,20}, {21,22,23,24,0},
    {1,6,11,16,21},  {2,7,12,17,21},  {3,8,13,18,21},   {4,9,14,19,21},   {5,10,15,20,21},
    {2,8,14,20,22},  {3,10,11,19,22}, {5,9,12,16,22},   {1,7,15,18,22},   {4,6,13,17,22},
    {3,9,15,17,23},  {5,6,14,18,23},  {4,7,11,20,23},   {2,10,13,16,23},  {1,8,12,19,23},
    {4,10,12,18,24}, {1,9,13,20,24},  {2,6,15,19,24},   {5,8,11,17,24},   {3,7,14,16,24},
    {5,7,13,19,0},   {4,8,15,16,0},   {1,10,14,17,0},   {3,6,12,20,0},    {2,9,11,18,0}
  }; 
  private int steps = 0;
  private boolean complete = false;
  class Node&lt;T extends Comparable&lt;T&gt;&gt; implements Comparable&lt;Node&lt;T&gt;&gt; {
    String label;
    T value;
    Node(String label, T value) {
      this.label = label;
      this.value = value;
    }
    @Override
    public String toString() {
      return label + ": " + value.toString();
    }
    @Override
    public int compareTo(Node&lt;T&gt; other) {
      return value.compareTo(other.value);
    }
  }
  // g represents all potential orders; starts as complete graph
  private ListenableGraph&lt;Node&lt;Integer&gt;, DefaultEdge&gt; g;
  // g1 represents all actual orders; starts with no edges
  private SimpleDirectedGraph&lt;Node&lt;Integer&gt;, DefaultEdge&gt; g1;
  private JGraphXAdapter&lt;Node&lt;Integer&gt;, DefaultEdge&gt; jgxAdapter;
  @SuppressWarnings("unchecked")
  Node&lt;Integer&gt;[] vertexArray = new Node[ARRAY_SIZE];
  List&lt;Set&lt;Node&lt;Integer&gt;&gt;&gt; connectedComponentsOfG;
  HashMap&lt;Node&lt;Integer&gt;,com.mxgraph.model.mxICell&gt; vertexToCellMap;
  HashMap&lt;DefaultEdge,com.mxgraph.model.mxICell&gt; edgeToCellMap;
  // sort sets in descending order by number of elements
  public class SetComparator implements Comparator&lt;Set&lt;Node&lt;Integer&gt;&gt;&gt; {
    @Override
    public int compare(Set&lt;Node&lt;Integer&gt;&gt; s1, Set&lt;Node&lt;Integer&gt;&gt; s2) {
      return s2.size() - s1.size();
    }
  }
  TransitiveClosure transitiveClosure = TransitiveClosure.INSTANCE;

  public FiveSortPanel() {
    restart();
  }

  public int getSteps() {
    return steps;
  }

  public boolean isComplete() {
    return complete;
  }

  private void updateConnectedComponents() {
    @SuppressWarnings("unchecked")
    StrongConnectivityInspector&lt;Node&lt;Integer&gt;,DefaultEdge&gt; sci 
      = new StrongConnectivityInspector&lt;Node&lt;Integer&gt;,DefaultEdge&gt;(
          (DirectedGraph&lt;Node&lt;Integer&gt;, DefaultEdge&gt;) g);
    connectedComponentsOfG = sci.stronglyConnectedSets();
    Collections.sort(connectedComponentsOfG, new SetComparator());
  }

  public void step() {
    if (!complete) {
      chooseFiveAndSort();
      ++steps;
    }
    updateConnectedComponents();
    complete = true;
    for (Set&lt;Node&lt;Integer&gt;&gt; s : connectedComponentsOfG) {
      if (s.size() &gt; 1) {
        complete = false;
      }
    }
  }

  public void restart() {
    removeAll();
    steps = 0;
    complete = false;
    shuffleBIBD();
    g = new ListenableDirectedGraph&lt;Node&lt;Integer&gt;, DefaultEdge&gt;(DefaultEdge.class);
    g1 = new SimpleDirectedGraph&lt;Node&lt;Integer&gt;, DefaultEdge&gt;(DefaultEdge.class);
    jgxAdapter = new JGraphXAdapter&lt;Node&lt;Integer&gt;, DefaultEdge&gt;(g);
    vertexToCellMap = jgxAdapter.getVertexToCellMap();
    edgeToCellMap = jgxAdapter.getEdgeToCellMap();
    jgxAdapter.getStylesheet().getDefaultEdgeStyle().put(mxConstants.STYLE_NOLABEL, "1");
    add(new mxGraphComponent(jgxAdapter));
    ArrayList&lt;Integer&gt; permutation = new ArrayList&lt;Integer&gt;();
    for (int i = 0; i &lt; ARRAY_SIZE; ++i) {
      permutation.add(i);
    }
    Collections.shuffle(permutation);
    @SuppressWarnings("unchecked")
    Node&lt;Integer&gt;[] n = new Node[ARRAY_SIZE];
    for (int i = 0; i &lt; ARRAY_SIZE; ++i) {
      n[i] = new Node&lt;Integer&gt;(ALPHABET.substring(i, i+1), permutation.get(i));
      vertexArray[i] = n[i];
      g.addVertex(n[i]);
      g1.addVertex(n[i]);
      for (int j = 0; j &lt; i; ++j) {
        g.addEdge(n[i], n[j]);
        g.addEdge(n[j], n[i]);
      }
    }
    updateConnectedComponents();
    mxCircleLayout layout = new mxCircleLayout(jgxAdapter);
    layout.execute(jgxAdapter.getDefaultParent());
    //repaint();
  }

  private void chooseFiveAndSort() {
    Node&lt;Integer&gt;[] fiveNodes = chooseFive();
    for (int i = 0; i &lt; fiveNodes.length-1; ++i) {
      g1.addEdge(fiveNodes[i],fiveNodes[i+1]);
    }
    transitiveClosure.closeSimpleDirectedGraph(g1);
    List&lt;Object&gt; edgeCellList = new ArrayList&lt;Object&gt;();
    for (int i = 0; i &lt; fiveNodes.length-1; ++i) {
      List&lt;Node&lt;Integer&gt;&gt; predList = Graphs.predecessorListOf(g1,fiveNodes[i]);
      predList.add(fiveNodes[i]);
      List&lt;Node&lt;Integer&gt;&gt; succList = Graphs.successorListOf(g1,fiveNodes[i+1]);
      succList.add(fiveNodes[i+1]);
      for (Node&lt;Integer&gt; np : predList) {
        for (Node&lt;Integer&gt; ns : succList) {
          g.removeEdge(ns,np);
          edgeCellList.add((Object)(edgeToCellMap.get(g.getEdge(np, ns))));
        }
      }
    }
    jgxAdapter.setCellStyle(STROKE_YELLOW, edgeCellList.toArray());
  }

  private Node&lt;Integer&gt;[] chooseFive() {
    return chooseFiveRandomBIBD();
  }

  private void shuffleBIBD() {
    List&lt;Integer[]&gt; BIBDList = (List&lt;Integer[]&gt;) Arrays.asList(BIBD);
    Collections.shuffle(BIBDList);
    BIBD = BIBDList.toArray(new Integer[0][0]);
  }

  private Node&lt;Integer&gt;[] chooseFiveRandomBIBD() {
    Integer[] indexArray = BIBD[steps];
    @SuppressWarnings("unchecked")
    Node&lt;Integer&gt;[] nodeArray = new Node[SORT_SIZE];
    for (int i = 0; i &lt; SORT_SIZE; ++i) {
      nodeArray[i] = vertexArray[indexArray[i]];
    }
    Arrays.sort(nodeArray);
    return nodeArray;
  }

}
</code></pre>
Given a machine that can sort 5 of your objects. How fast can we sort 25 of them?
<blockquote>
  <p>Assume that, you have <strong>25 objects</strong>, and  a <strong>machine that can sort 5 of them</strong> by some criteria that you don't even know. The cost of using this machine is very expensive (1$ for one launch), so what is the minimal cost of sorting all of your objects? </p>
</blockquote>

<p>My current solution is very simple (similar idea to <a href="https://en.wikipedia.org/wiki/Merge_sort">merge sort</a>):  </p>

<ol>
<li>Randomly divide them into 5 groups of 5 objects</li>
<li>Sort each of them (+5 launches)</li>
<li>Now, sort the minimal elements of these five groups (+1 launch)</li>
<li>Now we have the minimal element of the whole set. Remove it from the group that it's belong to, and repeat the step <strong>3</strong> until only 5 unsorted objects left in general (+19 launch)</li>
<li>Sort the rest 5 objects (+1 launch)</li>
</ol>

<p>So, in general, we have to pay <strong>26$</strong> (26 launches). </p>

<blockquote>
  <p>Question: Is there any way to make it cheaper (sort them in the least number of launches)?</p>
</blockquote>