Moises Gamio
Moises Gamio Software Engineer. Comprehensive experience in all phases of the software development lifecycle for several economic sectors.

Merge two Sorted Lists

Merge two Sorted Lists

A merging algorithm takes two sorted lists as input and produces a single list as output, containing all the elements of the two inputs lists in sorted order.

Problem

Given two sorted lists, merge them in a new sorted list.

merge-two-sorted-lists

Solution

We can join the two lists into a new list and apply a sort algorithm such as bubble sort, insertion, or quicksort. What we are going to do is to implement a new algorithm with a NlogN performance.

  • We define a new List to add all elements from the other two lists in a sorted way.
  • We define two indexes that point to every element in every list
  • We iterate both lists while still exist elements in both lists
  • We compare elements from both lists and add the smaller one to the new list in every iteration. Before passing to the next iteration, we increment in one the index of the list, which contains the smaller element.
  • If there is a list that still contains elements, we add them directly to the new list.

A test case helps to validate your assumptions

Our assumption based on a test case:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
@Test
public void mergeSortedLists() {
  List<Integer> sList1 = Arrays.asList(1,1,2,5,8);
  List<Integer> sList2 = Arrays.asList(3,4,6);
  assertEquals("[1, 1, 2, 3, 4, 5, 6, 8]",    
    SortedList.merge_sorted(sList1,sList2).toString());
}

@Test
public void mergeSortedLists2() {
  List<Integer> sList1 = Arrays.asList(2,4,5);
  List<Integer> sList2 = Arrays.asList(1,3,6);
  assertEquals("[1, 2, 3, 4, 5, 6]", 
    SortedList.merge_sorted(sList1,sList2).toString());
}

Here, the implementation code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
public class SortedList {
  public static List<Integer> merge_sorted(
    List<Integer> sList1, List<Integer> sList2) {

    List<Integer> mergedSortedList = new ArrayList<>();
    int idx1 = 0;
    int idx2 = 0;

    while (idx1 < sList1.size() && idx2 < sList2.size()) {
      if (sList1.get(idx1) <= sList2.get(idx2)) {
        mergedSortedList.add(sList1.get(idx1));
        idx1++;
      } else {
        mergedSortedList.add(sList2.get(idx2));
        idx2++;
      }
    }

    return mergedSortedList;
  }
}

The previous algorithm is missing how to proceed when one of the lists still contains elements not compared. Keep reading here