This isn't sorting correctly, I would like if someone can fix the mergeSort and merge method. I need to sort the list1 and list2 and then merge them back into empList. I don't know how to do this and would appreciate the help.

Thank you for the help.

import java.util.ArrayList; import java.util.List; import java.util.Random; class Employee { int salary; long id; public Employee(long id, int salary) { super(); this.salary = salary; this.id = id; } public int getSalary() { return salary; } public void setSalary(int salary) { this.salary = salary; } public long getId() { return id; } public void setId(long id) { this.id = id; } @Override public String toString() { return "Salary: " + salary + ", Id: " + id; } } public class ThreadSorting { public static void main(String[] args) { // TODO Auto-generated method stub ArrayList list1; ArrayList list2; long nextID = 0; ArrayList empList = new ArrayList(10000); // sort 10000 elements for (int i = 0; i < 10000; i++) { nextID++; Employee e = new Employee(nextID, getSalary());// fil with random ID and salary from the Employee class empList.add(e); // System.out.println(e.getID() + " " + e.getSalary()); } list1 = new ArrayList(); list2 = new ArrayList(); for (int i = 0; i < empList.size() / 2; i++) { list1.add(empList.get(i)); // fill the first half of the empList } for (int i = 0; i < empList.size() - empList.size() / 2; i++) { list2.add(empList.get(i)); // fill the second half of the empList } Thread thr1 = new Thread(new Runnable() { public void run() { function1(list1); // thread takes care of function 1 } }); Thread thr2 = new Thread(new Runnable() { public void run() { function2(list2); // takes care of function 2 } }); thr1.start(); thr2.start(); } public static void function1(ArrayList list1) { mergeSort(list1); } public static void function2(ArrayList list2) { mergeSort(list2); } public static void mergeSort(ArrayList list1) { ArrayList left = new ArrayList(); ArrayList right = new ArrayList(); for (int i = 0; i < list1.size() / 2; i++) { left.add(list1.get(i)); } for (int i = list1.size()/2+1; i < list1.size() ; i++) { right.add(list1.get(i)); } if(left.size()>right.size()) return; mergeSort(left); // right here is the problem mergeSort(right); // problem I'm getting merge(list1, left, right); } public static void merge(ArrayList list1, ArrayList left, ArrayList right) { int i = 0, j = 0; ArrayList temp = new ArrayList(); while (i < left.size() && j < right.size()) { if (left.get(i).getSalary() < right.get(j).getSalary()) { temp.add(left.get(i)); i++; } else { temp.add(right.get(j)); j++; } } while (i <= left.size()) { temp.add(left.get(i)); i++; } while (j > right.size()) { temp.add(right.get(j)); j++; } } public static int getSalary() { Random r = new Random(); return r.nextInt((4000 - 1500) + 1) + 1600; } }