Quick-sort algorithm implemented in chapel, I have used Task parallelism to improve upon it.

quick_sort.chpl

use List;
config var n_parallel = 4;

/**
    for partition of array on a pivot(last element)
    arguments
    arr int[] (ref)  -> array where the partition is done
    l int            -> left bound
    r int            -> right bound
    returns int      ->point of partition 
**/
proc partition(ref arr : [] int, l : int, r : int) : int {
    var pivot : int = arr[r];
    var i : int = (l - 1); 

    for j in l..(r-1) {
        if arr[j] < pivot {
            i += 1;
            arr[i] <=> arr[j];
        }
    }
    arr[i + 1] <=> arr[r];
    return (i + 1);
}

/**
    for processing all the bounds in a range(last element)
    arguments
    arr int[] (ref)             -> array used for sorting
    bounds  list((int, int))    -> list of all bounds
    start int                   -> start of range
    end int                     -> end of range
    returns list((int, int))    -> list of new_bounds
**/
proc process_bounds(ref arr : [] int, bounds : list((int, int)), start : int, end : int) : list((int, int)){
    var new_bounds : list((int, int));
    for (l, r) in bounds(start..end) {
        // check if it is a valid bound
        if l < r {
            var partition_point : int = partition(arr, l, r);

            new_bounds.append((l, partition_point - 1));
            new_bounds.append((partition_point + 1, r));
        }
    }
    return new_bounds;
}

/** 
    iterative process of quick sort using task parallelism for all bounds formed in one level
    arguments
    arr int[] (ref)  -> array to be sorted 
**/
proc quick_sort(ref arr : [] int){
    var n : int = arr.size;
    var flg : bool = true;

    // intial bound 0-n-1
    var bounds : list((int, int)) = [(0, n-1)];

    while flg {
        // to store new bounds formed in a level
        var new_bounds : list((int, int));
        var total_bounds : int = bounds.size;

        // not enough bounds serial processing
        if total_bounds < n_parallel then
            new_bounds.extend(process_bounds(arr, bounds, 0, total_bounds-1)); 
        // parallel proecessing in n_parallel stream
        else{
            var gap : int = total_bounds/n_parallel;

            // run n_parallel streams
            coforall itr in 0..(n_parallel-1) with (ref new_bounds) {
                // check end point to not exceed the range of bounds
                if((itr+1)*gap >= total_bounds) then
                new_bounds.extend(process_bounds(arr, bounds, itr*gap, total_bounds-1));
                else new_bounds.extend(process_bounds(arr, bounds, itr*gap, (itr+1)*gap-1));
            }
        }

        // checking is any new bounds formed
        // base case
        if new_bounds.size > 0 then bounds = new_bounds;
        else flg = false;
    }
}

var arr  = [4, 6, 2, 1, 5, 2, 9, 1, 0, 12, 1 , 4, 15];

// print unsorted array
write("array : ");
for i in arr do write(i, " ");
writeln();

quick_sort(arr);

// print sorted array
write("sorted array : ");
for i in arr do write(i, " ");
writeln();