import java.util.Arrays;

class BubbleSortThread extends Thread { private int[] arr;

BubbleSortThread(int[] arr) {
    this.arr = arr;
}

@Override
public void run() {
    int n = arr.length;
    for (int i = 0; i < n - 1; i++) {
        for (int j = 0; j < n - i - 1; j++) {
            if (arr[j] > arr[j + 1]) {
                int temp = arr[j];
                arr[j] = arr[j + 1];
                arr[j + 1] = temp;
            }
        }
    }
}

}

public class ParallelBubbleSort { private static int[] mergeSortedArrays(int[][] arrays) { int totalLength = 0; for (int[] array : arrays) { totalLength += array.length; }

    int[] result = new int[totalLength];
    int[] indexes = new int[arrays.length];

    for (int i = 0; i < totalLength; i++) {
        int minVal = Integer.MAX_VALUE;
        int minIdx = -1;

        for (int j = 0; j < arrays.length; j++) {
            if (indexes[j] < arrays[j].length && arrays[j][indexes[j]] < minVal) {
                minVal = arrays[j][indexes[j]];
                minIdx = j;
            }
        }

        result[i] = minVal;
        indexes[minIdx]++;
    }

    return result;
}

public static int[] parallelBubbleSort(int[] arr, int numThreads) {
    int chunkSize = arr.length / numThreads;
    BubbleSortThread[] threads = new BubbleSortThread[numThreads];
    int[][] sortedArrays = new int[numThreads][];

    // Create and start sorting threads
    for (int i = 0; i < numThreads; i++) {
        int start = i * chunkSize;
        int end = (i != numThreads - 1) ? (start + chunkSize) : arr.length;
        int[] subArray = Arrays.copyOfRange(arr, start, end);
        threads[i] = new BubbleSortThread(subArray);
        threads[i].start();
    }

    // Wait for all threads to finish
    for (BubbleSortThread thread : threads) {
        try {
            thread.join();
        } catch (InterruptedException e) {
            e.printStackTrace();
        }
    }

    // Retrieve sorted sub-arrays
    for (int i = 0; i < numThreads; i++) {
        sortedArrays[i] = threads[i].arr;
    }

    // Merge sorted sub-arrays
    int[] sortedArray = mergeSortedArrays(sortedArrays);
    return sortedArray;
}

// Sequential bubble sort
public static void sequentialBubbleSort(int[] arr) {
    int n = arr.length;
    for (int i = 0; i < n - 1; i++) {
        for (int j = 0; j < n - i - 1; j++) {
            if (arr[j] > arr[j + 1]) {
                int temp = arr[j];
                arr[j] = arr[j + 1];
                arr[j + 1] = temp;
            }
        }
    }
}

public static void main(String[] args) {
    int[] arr = new int[40000];
    for (int i = 0; i < 40000; i++) {
        arr[i] = (int) (Math.random() * 1000);
    }