1. Сортировать данные по индексу и второму столбцу
2. MergeSort использует в 2 раза больше оперативной памяти, нежели действительно требуется. В оперативной лучше сортировать по QuickSort (сортировка по умолчанию Arrays.sort()), тогда можно сортировать в 2 раза больше данных.
3. Так как дата представляется целым числом, можно использовать поразрядную сортировку (которая производит несколько сортировок подсчетом). Она еще быстрее. То есть, если дата представляется числом < 10^18, то сортировку можно произвести всего лишь тремя сортировками подсчетом (по разряду 10^6), которые выполняются за линейное время
4. ArrayList работает долго. Используйте массив
5. Не понял, как именно вы сливаете файлы. Их надо сливать по аналогии с MergeSort. То есть не последовательно, а также логарифмически