Bugged MergeSort in Java

Question

I'm using a dynamic array using a List and ArrayList classes. I think the bug is the merge method, but I don't what is wrong. I've used the "same" code in JS and Python and everything goes like it is suppose to go.

import java.util.ArrayList;
import java.util.List;

public class mergeS {

    private static List<Integer> numbers = new ArrayList<Integer>();
    private static int lon = 8;

    public static void main(String[] args) {
        long start, end;
        float time;
        for(int i = 0; i < lon; i++) {
            if(Math.random() < 0.5) {
                numbers.add((int)(Math.random()*(100)));
            }else {
                numbers.add((int)(-1*Math.random()*(100)));
            }
        }
        System.out.println("Unsorted list:\n"+numbers+"\n");
        start = System.nanoTime();
        mergeSort(numbers);
        end = System.nanoTime();
        time = (float) ((end-start)/Math.pow(10, 9));
        System.out.println("Sorted list:\n"+numbers);
        System.out.println("The time used was: "+time);
    }

    private static void mergeSort(List<Integer> numbers) {
        if (numbers.size() < 2) {
            return;
        }
        int mid = numbers.size() / 2;
        List<Integer> left = numbers.subList(0, mid);
        List<Integer> right = numbers.subList(mid, numbers.size());
        mergeSort(left);
        mergeSort(right);
        merge(left, right, numbers);
    }

    private static void merge(List<Integer> left, 
                            List<Integer> right, 
                            List<Integer> numbers) {
        int i = 0, j = 0, k = 0;
        while(i < left.size() && j < right.size()) {
            if(left.get(i) <= right.get(j)) {
                numbers.set(k, left.get(i));
                i++;
            }else {
                numbers.set(k, right.get(j));
                j++;
            }
            k++;
        }
        while(i < left.size()) {
            numbers.set(k, left.get(i));
            i++;
            k++;
        }
        while(j < right.size()) {
            numbers.set(k, right.get(j));
            j++;
            k++;
        }
    }

}

Please read: [How to debug small programs](https://ericlippert.com/2014/03/05/how-to-debug-small-programs/) — Turing85, Jan 06 '20 at 19:09
My code was right, the problem was that I didn't know that ```List.subList``` didn't create a new object. — Anthony Luzquiños, Jan 06 '20 at 20:59

score 1 · Accepted Answer · answered Jan 06 '20 at 20:23

1

Your code is fine, you've just missed that List.subList doesn't create a new object for you. It only returns the reference to the same numbers array. Once you'd replace

    List<Integer> left = numbers.subList(0, mid);
    List<Integer> right = numbers.subList(mid, numbers.size());

with

    List<Integer> left = new ArrayList<Integer>( numbers.subList( 0, mid ) );
    List<Integer> right = new ArrayList<Integer>( numbers.subList( mid, numbers.size() ) );

everything works like a charm.

answered Jan 06 '20 at 20:23

John Smith

427
6
17

I've verificated that my code was right using ```arrays``` instead of ```List```. I will try what you said. I didn't know that ```Lis.subList``` didn't create a new object. – Anthony Luzquiños Jan 06 '20 at 20:57

Bugged MergeSort in Java

1 Answers1