Can TableSort be used without a query?
Thanks to Berdir I got it working. This is how it works in more detail.

Tablesort is triggered "automatically" if the (column) arrays in the $headers array contains the keys 'data', 'field' and optionally 'sort'. This will create links with 'sort' and 'order' in the column headers and show the little arrow and such. 

To do your own sorting, get the current sort settings with tablesort_get_order and tablesort_get_sort and use those values for your own sorting function. The key 'sql' in the array returned by tablesort_get_order contains the field name to be used for sorting.

A piece of (untested) example code with the array $users containing some details for each user:

// setup the table data that we want to show
$tableData = array();
foreach ($users as $userDetails) {
  $tableData[] = array(
      'name' =&gt; $userDetails['name'],
      'visits' =&gt; $userDetails['visits'],
      'views' =&gt; $userDetails['views'],
      'comments' =&gt; $userDetails['comments']
  );
}

// headers array, sorting by default on comments
$headers = array(
    array('data' =&gt; t('Name'), 'field' =&gt; 'name'),
    array('data' =&gt; t('Visits'), 'field' =&gt; 'visits'),
    array('data' =&gt; t('Views'), 'field' =&gt; 'views'),
    array('data' =&gt; t('Comments'), 'field' =&gt; 'comments', 'sort' =&gt; 'desc')
);

// getting the current sort and order parameters from the url
$order = tablesort_get_order($headers);
$sort = tablesort_get_sort($headers);

// sort the table data accordingly (write your own sort function)
$tableData = my_array_sort($tableData, $order['sql'], $sort);

// create the array with rows for theme table
$rows = array();
foreach ($tableData as $entry) {
  $rows[] = array(
      array('data' =&gt; $entry['name']),
      array('data' =&gt; $entry['visits']),
      array('data' =&gt; $entry['views']),
      array('data' =&gt; $entry['comments']),
  );
}

// add any attributes and sent everything to theme table
$attributes = array('class' =&gt; array('my_class'));
$table = array('header' =&gt; $headers, 'attributes' =&gt; $attributes, 'rows' =&gt; $rows);
$html = theme('table', $table);