Why is my raster view uninteresting faster than my merge?

Question

I am working on Saws programming, and the first essay is about sorting numbers in a known range. As an intelligent solution, they offer a raster image implementation by setting all the numbers in the input file to one of the raster images, and then simply repeating it to print the result. This is supposed to be much faster than a more traditional sorting algorithm such as quicksort or mergesort.

To test this, I myself wrote a bitmap in Java. I was not too surprised when I found out that the Unix sort command, which uses merge sort, is still much faster. I explained this by saying that it is written in C and is probably very optimized by some very smart people.

So then I wrote my own type of merge, also in Java. To my surprise, my BitmapSort was faster, but only marginally. With a very large input file (+ -800000 integers), bitmapsort is only 30% faster.

Here is my bitmap and bitmap implementation:

import java.util.Scanner;
import java.io.FileReader;
import java.io.File;

class BitmapSort {
    Scanner sc;

    BitmapSort() throws Exception {
        sc = new Scanner(new File("numbers.txt"));
    }

    void start() {
        BitMap map = new BitMap(3000000);
        while (sc.hasNextInt()) {
            map.set(sc.nextInt());
        }
        for (int i = 0; i < 3000000; i++) {
            if (map.isSet(i)) {
                System.out.println(i);
            }
        }
    }

    public static void main(String[] args) throws Exception {
        new BitmapSort().start();
    }
}


class BitMap {

    byte[] bits;
    int size;


    BitMap(int n) {
        size = n;
        bits = new byte[(int) Math.ceil((double) n / (double) Byte.SIZE)];
        for (Byte b : bits) {
            b = 0;
        }
    }

    private String toBinary(byte b) {
        return String.format(Integer.toBinaryString(b & 0xFF)).replace(' ', '0');
    }

    void set(int i) {
        int index = i / Byte.SIZE;
        bits[index] = (byte) ((bits[index] | (byte) (1 << (Byte.SIZE - 1 - (i % Byte.SIZE)))));
    }

    void unset(int i) {
        int index = i / Byte.SIZE;
        bits[index] = (byte) ((bits[index] ^ (byte) (1 << (Byte.SIZE - 1 - (i % Byte.SIZE)))));
    }

    boolean isSet(int i) {
        int index = i / Byte.SIZE;
        byte mask = (byte) ((bits[index] & (byte) (1 << (Byte.SIZE - 1 - (i % Byte.SIZE)))));
        return (bits[index] & mask) != 0;
    }

}

and here is my merger:

import java.util.Scanner;
import java.io.FileReader;
import java.io.File;

class MergeSort {
    Scanner sc;
    static int times;

    MergeSort() throws Exception {
        sc = new Scanner(new File("numbers.txt"));
        times = 0;
    }


    int[] mergeSort(int[] input) {
        if (input.length <= 1) {
            return input;
        }

        int middle = input.length / 2;

        int[] left = new int[middle];
        int[] right;
        if (input.length % 2 == 0) {
            right = new int[middle];
        } else {
            right = new int[middle + 1];
        }

        for (int i = 0; i < middle; i++) {
            left[i] = input[i];
        }
        for (int i = middle; i < input.length; i++) {
            right[i - middle] = input[i];
        }
        left = mergeSort(left);
        right = mergeSort(right);
        return merge(left, right);
    }

    int[] merge(int[] left, int[] right) {
        times++;
        int[] result = new int[left.length + right.length];
        int left_size = 0;
        int right_size = 0;
        int result_size = 0;
        while (left_size < left.length || right_size < right.length) {
            if (left_size < left.length && right_size < right.length) {
                if (left[left_size] <= right[right_size]) {
                    result[result_size] = left[left_size];
                    left_size++;
                    result_size++;
                } else {
                    result[result_size] = right[right_size];
                    right_size++;
                    result_size++;
                }
            } else if (left_size < left.length) {
                result[result_size] = left[left_size];
                left_size++;
                result_size++;
            } else if (right_size < right.length) {
                result[result_size] = right[right_size];
                right_size++;
                result_size++;
            }
        }
        return result;
    }

    void start() {
        int[] input = new int[838662];
        int i = 0;
        while (sc.hasNextInt()) {
            input[i] = sc.nextInt();
            i++;
        }


        int[] result = mergeSort(input);
        for (int j : result) {
            System.out.printf("%d\n", j);
        }
    }


    public static void main(String[] args) throws Exception {
        new MergeSort().start();
    }
}

The input file contains integers between 0and 3000000and contains numbers 838661. Please excuse the ugly coding style, it would just mean a quick comparison.

Thanks in advance! Sincerely, Linus

Answer 1

, " " , , . 800 , . Mergesorts .