Потоковая сортировка работает медленнее, чем безпоточная сортировка

Прежде всего, как вы измеряете прошедшее время? Вы выполняете оба теста в одной программе? Если это так, имейте в виду, что сортировка слиянием, вероятно, подвергнется компиляции Hotspot во время выполнения первого теста. Я предлагаю вам запускать каждый метод дважды, измеряя время при втором запуске.

Сколько процессоров/ядер у вас есть? Одна из проблем с этим кодом заключается в том, что основной поток тратит процессорное время на цикл while(!allThreadsTerminated), активно проверяя состояние потока. Если у вас один ЦП - вы тратите его впустую, вместо того, чтобы заниматься фактической сортировкой.

Замените цикл while на:

 for(counter=0; counter<files.length; counter++) {
        threadList[counter].join();
 }

Вы должны использовать Stream и стандартную сортировку:

static String[] sort(File[] files, boolean parallel) {
    return (parallel ? Stream.of(files).parallel() : Stream.of(files))
        .flatMap(f -> {
            try {
                return Files.lines(f.toPath());
            } catch (Exception e) {
                e.printStackTrace();
                return null;
            }
        })
        .sorted()
        .toArray(String[]::new);
}

static String[] sort(File[] files) {
    return sort(files, false);
}

static String[] threadSort(File[] files) {
    return sort(files, true);
}

В моей среде threadSort работает быстрее.

sort:
files=511 sorted lines=104419 elapse=4784ms
threadSort:
files=511 sorted lines=104419 elapse=3060ms

Вы можете использовать java.util.concurrent.ExecutorService, который будет запускать все ваши задачи в указанном количестве потоков, и как только все потоки закончат выполнение, вы получите объект списка Future, который будет содержать результат выполнения каждого потока. Список будущих объектов будет в том же порядке, в котором вы вставили вызываемые объекты в его список.

Для этого в первую очередь вам понадобится SortingThread реализовать Callable интерфейс, чтобы вы могли получать результат выполнения каждого потока.
Каждый Callable объект должен реализовывать метод call(), а его возвращаемый тип будет вашим Future объектом.

    public class SortingThread implements Callable<String[]> {
    String[] data;
    SortingThread(String[] data) {
        this.data = data;
    }
    @Override
    public String[] call() throws Exception {
        data = MergeSort.mergeSort(data);
        return data;
    }  
   }

Далее вам нужно использовать ExecutorSerivce для управления потоками.

public static String[] sortingExampleWithMultiThreads(File[] files) throws IOException {
      String sortedData[] = new String[0]; 
      int counter = 0; 
      boolean allThreadsTerminated = false;
      SortingThread[] threadList = new SortingThread[files.length];
      ArrayList<Callable<String[]>> callableList = new ArrayList<Callable<String[]>>();
      for (File file : files) {
          String[] data = getData(file);
          callableList.add(new SortingThread(data));  //Prepare a Callable list which would be passed to invokeAll() method.
          counter++;
      }

      ExecutorService service = Executors.newFixedThreadPool(counter);  // Create a fixed size thread pool, one thread for each file processing...
      List<Future<String[]>> futureObjects = service.invokeAll(callableList);  //List of what call() method of SortingThread is returning...

      for(counter=0; counter<files.length; counter++) {
          sortedData = MergeSort.merge(sortedData, futureObjects.get(counter));
      }
      return sortedData;
 }

Таким образом вы можете избежать использования цикла WHILE, который, как известно, увеличивает загрузку ЦП (следовательно, снижает скорость), и если у вас одноядерный ЦП, то он может достичь 100% использования, а если двухъядерный, то 50%.
Кроме того, использование ExecutorService для управления потоками является лучшим способом при работе с многопоточностью вместо того, чтобы разработчик запускал и отслеживал потоки для получения результатов. Таким образом, вы можете рассчитывать на производительность.

Я не запускал его, поэтому вам, возможно, придется внести изменения здесь и там, но я выделил ваш подход.

P.S.: Чтобы получить аккуратные и точные результаты при измерении производительности, всегда создавайте новый экземпляр JVM для каждого запуска.