Merge log files into one big log file

MergeLogFiles.java

import java.time.LocalTime;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.List;

/**
 * Time complexity: O(m * n * log m)
 * Space complexity: O(m * n)
 *
 * m -> total number of log files
 * n -> average entries in each log file
 */
public class MergeLogFiles {

    public static List<String> mergeLogFiles(List<List<String>> logs) {
        // Special case
        if (logs == null || logs.size() == 0) {
            return Collections.emptyList();
        }
        // List to store the sorted logs
        List<List<String>> sortedLogs = new ArrayList<>();
        // Loop until there is only one element left in the logs
        // list which will represent the flat list of sorted items.
        while (logs.size() != 1) {
            // Clear the elements from the previous list
            sortedLogs.clear();
            // Loop through all the individual log files
            for (int i = 0; i < logs.size(); i += 2) {
                // Add the last log file as is
                if (i == logs.size() - 1) {
                    sortedLogs.add(logs.get(i));
                }
                // Take two files at a time and sort them
                else {
                    sortedLogs.add(merge(logs.get(i), logs.get(i + 1)));
                }
            }
            // Create a new list to avoid pointing to same reference
            logs = new ArrayList<>(sortedLogs);
        }
        return sortedLogs.get(0);
    }

    private static List<String> merge(List<String> left, List<String> right) {
        List<String> sortedList = new ArrayList<>();
        // Pointers for both lists
        int i = 0;
        int j = 0;
        // Loop through the lists
        while (i < left.size() && j < right.size()) {
            // Get the timestamp from the log entry
            String leftTime = left.get(i).split(" ")[0];
            String rightTime = right.get(j).split(" ")[0];
            // Convert the time to LocalTime to compare
            LocalTime localTimeLeft = LocalTime.parse(leftTime);
            LocalTime localTimeRight = LocalTime.parse(rightTime);
            // Compare the timestamps and add smaller to the list
            if (localTimeLeft.isBefore(localTimeRight)) {
                sortedList.add(left.get(i));
                i++;
            } else {
                sortedList.add(right.get(j));
                j++;
            }
        }
        // Add remaining elements from left and right lists
        while (i < left.size()) {
            sortedList.add(left.get(i));
            i++;
        }
        while (j < right.size()) {
            sortedList.add(right.get(j));
            j++;
        }
        return sortedList;
    }

    public static void main(String[] args) {
        List<String> log1 = Arrays.asList(
                "07:35:02 log1 msg1",
                "07:35:03 log1 msg2",
                "07:35:03 log1 msg3",
                "07:35:15 log1 msg4"
        );
        List<String> log2 = Arrays.asList(
                "07:34:43 log2 msg1",
                "07:35:16 log2 msg2",
                "07:36:15 log2 msg3"
        );
        List<String> log3 = Arrays.asList(
                "06:53:48 log3 msg1",
                "07:23:27 log3 msg2",
                "07:33:27 log3 msg3",
                "07:34:27 log3 msg4",
                "07:35:28 log3 msg5"
        );
        List<List<String>> logs = Arrays.asList(log1, log2, log3);
        List<String> sortedLogs = mergeLogFiles(logs);
        for (String sortedLog : sortedLogs) {
            System.out.println(sortedLog);
        }
    }
}