I'm working on modernizing Rosetta Code's infrastructure. Starting with communications. Please accept this time-limited open invite to RC's Slack.. --Michael Mol (talk) 20:59, 30 May 2020 (UTC)

# Common sorted list

Common sorted list is a draft programming task. It is not yet considered ready to be promoted as a complete task, for reasons that should be found in its talk page.

Sorting Algorithm
This is a sorting algorithm.   It may be applied to a set of data in order to sort it.     For comparing various sorts, see compare sorts.   For other sorting algorithms,   see sorting algorithms,   or:

O(n logn) sorts

O(n log2n) sorts
Shell Sort

Given an integer array nums, the goal is create common sorted list with unique elements.

Example

nums = [5,1,3,8,9,4,8,7], [3,5,9,8,4], [1,3,7,9]

output = [1,3,4,5,7,8,9]

## 11l

`F csl(nums)   Set[Int] r   L(num) nums      r.update(num)   R sorted(Array(r)) print(csl([[5, 1, 3, 8, 9, 4, 8, 7], [3, 5, 9, 8, 4], [1, 3, 7, 9]]))`
Output:
```[1, 3, 4, 5, 7, 8, 9]
```

## Action!

`INCLUDE "D2:SORT.ACT" ;from the Action! Tool Kit DEFINE PTR="CARD" PROC PrintArray(BYTE ARRAY a BYTE len)  BYTE i   Print("  [")  IF len>0 THEN    FOR i=0 TO len-1    DO      PrintB(a(i))      IF i<len-1 THEN Put(' ) FI    OD  FI  PrintE("]")RETURN BYTE FUNC Contains(BYTE ARRAY a BYTE len,value)  BYTE i   IF len>0 THEN    FOR i=0 TO len-1    DO      IF a(i)=value THEN RETURN(1) FI    OD  FIRETURN (0) PROC CommonListElements(PTR ARRAY arrays  BYTE ARRAY lengths BYTE count  BYTE ARRAY res BYTE POINTER resLen)   BYTE ARRAY a  BYTE i,j,len,value,cnt,maxcnt   resLen^=0  IF count=0 THEN    RETURN  ELSEIF count=1 THEN    MoveBlock(res,a,len) RETURN  FI   FOR i=0 TO count-1  DO    a=arrays(i) len=lengths(i)    IF len>0 THEN      FOR j=0 TO len-1      DO        value=a(j)        IF Contains(res,resLen^,value)=0 THEN          res(resLen^)=value resLen^==+1        FI      OD    FI  OD  SortB(res,resLen^,0)RETURN PROC Test(PTR ARRAY arrays BYTE ARRAY lengths BYTE count)  BYTE ARRAY res(100)  BYTE len,i   CommonListElements(arrays,lengths,count,res,@len)  PrintE("Input:")  FOR i=0 TO count-1  DO    PrintArray(arrays(i),lengths(i))  OD  PrintE("Output:")  PrintArray(res,len) PutE()RETURN PROC Main()  PTR ARRAY arrays(3)  BYTE ARRAY    lengths(3)=[8 5 4],    a1(8)=[5 1 3 8 9 4 8 7],    a2(5)=[3 5 9 8 4],    a3(4)=[1 3 7 9],    a4(8)=[5 1 1 1 9 9 8 7],    a5(5)=[5 5 9 9 9],    a6(4)=[1 7 7 9]  BYTE len   Put(125) PutE() ;clear the screen   arrays(0)=a1 arrays(1)=a2 arrays(2)=a3  Test(arrays,lengths,3)   arrays(0)=a4 arrays(1)=a5 arrays(2)=a6  Test(arrays,lengths,3)   lengths(0)=0  Test(arrays,lengths,3)RETURN`
Output:
```Input:
[5 1 3 8 9 4 8 7]
[3 5 9 8 4]
[1 3 7 9]
Output:
[1 3 4 5 7 8 9]

Input:
[5 1 1 1 9 9 8 7]
[5 5 9 9 9]
[1 7 7 9]
Output:
[1 5 7 8 9]

Input:
[]
[5 5 9 9 9]
[1 7 7 9]
Output:
[1 5 7 9]
```

`with Ada.Text_Io;with Ada.Containers.Vectors; procedure Sorted is    package Integer_Vectors is     new Ada.Containers.Vectors (Index_Type   => Positive,                                 Element_Type => Integer);   use Integer_Vectors;    package Vector_Sorting is     new Integer_Vectors.Generic_Sorting;   use Vector_Sorting;    procedure Unique (Vec : in out Vector) is      Res : Vector;   begin      for E of Vec loop         if Res.Is_Empty or else Res.Last_Element /= E then            Res.Append (E);         end if;      end loop;      Vec := Res;   end Unique;    procedure Put (Vec : Vector) is      use Ada.Text_Io;   begin      Put ("[");      for E of Vec loop         Put (E'Image);  Put (" ");      end loop;      Put ("]");      New_Line;   end Put;    A : constant Vector := 5 & 1 & 3 & 8 & 9 & 4 & 8 & 7;   B : constant Vector := 3 & 5 & 9 & 8 & 4;   C : constant Vector := 1 & 3 & 7 & 9;   R : Vector          := A & B & C;begin   Sort (R);   Unique (R);   Put (R);end Sorted;`
Output:
`[ 1  3  4  5  7  8  9 ]`

## APL

Works with: Dyalog APL
`csl ← (⊂∘⍋⌷⊢)∪∘∊`
Output:
```      csl (5 1 3 8 9 4 8 7)(3 5 9 8 4)(1 3 7 9)
1 3 4 5 7 8 9```

## AppleScript

`use AppleScript version "2.4" -- OS X 10.10 (Yosemite) or lateruse framework "Foundation" local nums, output set nums to current application's class "NSArray"'s arrayWithArray:({{5, 1, 3, 8, 9, 4, 8, 7}, {3, 5, 9, 8, 4}, {1, 3, 7, 9}})set output to (nums's valueForKeyPath:("@distinctUnionOfArrays.self"))'s sortedArrayUsingSelector:("compare:")return output as list`
Output:
`{1, 3, 4, 5, 7, 8, 9}`

Or, as a composition of slightly more commonly-used generic functions (given that distinctUnionOfArrays is a relatively specialised function, while concat/flatten and nub/distinct are more atomic, and more frequently reached for):

`use AppleScript version "2.4"use framework "Foundation"  ------------------- COMMON SORTED ARRAY ------------------on run    sort(nub(concat({¬        {5, 1, 3, 8, 9, 4, 8, 7}, ¬        {3, 5, 9, 8, 4}, ¬        {1, 3, 7, 9}})))end run  -------------------- GENERIC FUNCTIONS ------------------- -- concat :: [[a]] -> [a]on concat(xs)    ((current application's NSArray's arrayWithArray:xs)'s ¬        valueForKeyPath:"@unionOfArrays.self") as listend concat  -- nub :: [a] -> [a]on nub(xs)    ((current application's NSArray's arrayWithArray:xs)'s ¬        valueForKeyPath:"@distinctUnionOfObjects.self") as listend nub  -- sort :: Ord a => [a] -> [a]on sort(xs)    ((current application's NSArray's arrayWithArray:xs)'s ¬        sortedArrayUsingSelector:"compare:") as listend sort`
Output:
`{1, 3, 4, 5, 7, 8, 9}`

## AutoHotkey

`Common_sorted_list(nums){    elements := [], output := []    for i, num in nums        for j, d in num            elements[d] := true    for val, bool in elements        output.push(val)    return output}`
Examples:
`nums := [[5,1,3,8,9,4,8,7], [3,5,9,8,4], [1,3,7,9]]output := Common_sorted_list(nums)return`
Output:
`[1, 3, 4, 5, 6, 7, 9]`

## AWK

` # syntax: GAWK -f COMMON_SORTED_LIST.AWKBEGIN {    PROCINFO["sorted_in"] = "@ind_num_asc"    nums = "[5,1,3,8,9,4,8,7],[3,5,9,8,4],[1,3,7,9]"    printf("%s : ",nums)    n = split(nums,arr1,"],?") - 1    for (i=1; i<=n; i++) {      gsub(/[\[\]]/,"",arr1[i])      split(arr1[i],arr2,",")      for (j in arr2) {        arr3[arr2[j]]++      }    }    for (j in arr3) {      printf("%s ",j)    }    printf("\n")    exit(0)} `
Output:
```[5,1,3,8,9,4,8,7],[3,5,9,8,4],[1,3,7,9] : 1 3 4 5 7 8 9
```

## C

`#include <stdio.h>#include <stdlib.h>#include <string.h> #define COUNTOF(a) (sizeof(a)/sizeof(a[0])) void fatal(const char* message) {    fprintf(stderr, "%s\n", message);    exit(1);} void* xmalloc(size_t n) {    void* ptr = malloc(n);    if (ptr == NULL)        fatal("Out of memory");    return ptr;} int icompare(const void* p1, const void* p2) {    const int* ip1 = p1;    const int* ip2 = p2;    return (*ip1 < *ip2) ? -1 : ((*ip1 > *ip2) ? 1 : 0);} size_t unique(int* array, size_t len) {    size_t out_index = 0;    int prev;    for (size_t i = 0; i < len; ++i) {        if (i == 0 || prev != array[i])            array[out_index++] = array[i];        prev = array[i];    }    return out_index;} int* common_sorted_list(const int** arrays, const size_t* lengths, size_t count, size_t* size) {    size_t len = 0;    for (size_t i = 0; i < count; ++i)        len += lengths[i];    int* array = xmalloc(len * sizeof(int));    for (size_t i = 0, offset = 0; i < count; ++i) {        memcpy(array + offset, arrays[i], lengths[i] * sizeof(int));        offset += lengths[i];    }    qsort(array, len, sizeof(int), icompare);    *size = unique(array, len);    return array;} void print(const int* array, size_t len) {    printf("[");    for (size_t i = 0; i < len; ++i) {        if (i > 0)            printf(", ");        printf("%d", array[i]);    }    printf("]\n");} int main() {    const int a[] = {5, 1, 3, 8, 9, 4, 8, 7};    const int b[] = {3, 5, 9, 8, 4};    const int c[] = {1, 3, 7, 9};    size_t len = 0;    const int* arrays[] = {a, b, c};    size_t lengths[] = {COUNTOF(a), COUNTOF(b), COUNTOF(c)};    int* sorted = common_sorted_list(arrays, lengths, COUNTOF(arrays), &len);    print(sorted, len);    free(sorted);    return 0;}`
Output:
```[1, 3, 4, 5, 7, 8, 9]
```

## C++

`#include <iostream>#include <vector>#include <set>#include <algorithm> template<typename T>std::vector<T> common_sorted_list(const std::vector<std::vector<T>>& ll) {    std::set<T> resultset;    std::vector<T> result;    for (auto& list : ll)        for (auto& item : list)            resultset.insert(item);    for (auto& item : resultset)        result.push_back(item);     std::sort(result.begin(), result.end());    return result;} int main() {    std::vector<int> a = {5,1,3,8,9,4,8,7};    std::vector<int> b = {3,5,9,8,4};    std::vector<int> c = {1,3,7,9};    std::vector<std::vector<int>> nums = {a, b, c};     auto csl = common_sorted_list(nums);    for (auto n : csl) std::cout << n << " ";    std::cout << std::endl;     return 0;}`
Output:
`1 3 4 5 7 8 9`

## Excel

### LAMBDA

Binding the name COMMONSORTED to the following lambda expression in the Name Manager of the Excel WorkBook:

`COMMONSORTED=LAMBDA(grid,    SORT(        UNIQUE(            CONCATCOLS(grid)        )    ))`

and also assuming the following generic bindings in the Name Manager for the WorkBook:

`CONCATCOLS=LAMBDA(cols,    LET(        nRows, ROWS(cols),        ixs, SEQUENCE(            COLUMNS(cols) * nRows, 1,            1, 1        ),         FILTERP(            LAMBDA(x, 0 < LEN("" & x))        )(            INDEX(cols,                LET(                    r, MOD(ixs, nRows),                     IF(0 = r, nRows, r)                ),                1 + QUOTIENT(ixs - 1, nRows)            )        )    ))  FILTERP=LAMBDA(p,    LAMBDA(xs,        FILTER(xs, p(xs))    ))`

The formula in cell B2 defines a dynamic array of values, additionally populating further cells in column B.

Output:
 =COMMONSORTED(C2:E9) fx A B C D E 1 Common sorted 2 1 5 3 1 3 3 1 5 3 4 4 3 9 7 5 5 8 8 9 6 7 9 4 7 8 4 8 9 8 9 7

## F#

` // Common sorted list. Nigel Galloway: February 25th., 2021let nums=[|[5;1;3;8;9;4;8;7];[3;5;9;8;4];[1;3;7;9]|]printfn "%A" (nums|>Array.reduce(fun n g->[email protected])|>List.distinct|>List.sort) `
Output:
```[1; 3; 4; 5; 7; 8; 9]
```

## Factor

Note: in older versions of Factor, `union-all` is called `combine`.

Works with: Factor version 0.99 2021-02-05
`USING: formatting kernel sets sorting ; { { 5 1 3 8 9 4 8 7 } { 3 5 9 8 4 } { 1 3 7 9 } }dup union-all natural-sort"Sorted union of %u is:\n%u\n" printf`
Output:
```Sorted union of { { 5 1 3 8 9 4 8 7 } { 3 5 9 8 4 } { 1 3 7 9 } } is:
{ 1 3 4 5 7 8 9 }
```

## Go

Translation of: Wren
`package main import (    "fmt"    "sort") func distinctSortedUnion(ll [][]int) []int {    var res []int    for _, l := range ll {        res = append(res, l...)    }    set := make(map[int]bool)    for _, e := range res {        set[e] = true    }    res = res[:0]    for key := range set {        res = append(res, key)    }    sort.Ints(res)    return res} func main() {    ll := [][]int{{5, 1, 3, 8, 9, 4, 8, 7}, {3, 5, 9, 8, 4}, {1, 3, 7, 9}}    fmt.Println("Distinct sorted union of", ll, "is:")    fmt.Println(distinctSortedUnion(ll))}`
Output:
```Distinct sorted union of [[5 1 3 8 9 4 8 7] [3 5 9 8 4] [1 3 7 9]] is:
[1 3 4 5 7 8 9]
```

`import Data.List (nub, sort) -------------------- COMMON SORTED LIST ------------------ commonSorted :: Ord a => [[a]] -> [a]commonSorted = sort . nub . concat --------------------------- TEST -------------------------main :: IO ()main =  print \$    commonSorted      [ [5, 1, 3, 8, 9, 4, 8, 7],        [3, 5, 9, 8, 4],        [1, 3, 7, 9]      ]`
Output:
`[1,3,4,5,7,8,9]`

## J

`csl =: /:[email protected][email protected];`
Output:
```   nums =: 5 1 3 8 9 4 8 7;3 5 9 8 4;1 3 7 9
csl nums
1 3 4 5 7 8 9```

## JavaScript

`(() => {    "use strict";     // --------------- COMMON SORTED LIST ----------------     // commonSorted :: Ord a => [[a]] -> [a]    const commonSorted = xs =>        sort(nub(concat(xs)));      // ---------------------- TEST -----------------------    const main = () =>        commonSorted([            [5, 1, 3, 8, 9, 4, 8, 7],            [3, 5, 9, 8, 4],            [1, 3, 7, 9]        ]);      // --------------------- GENERIC ---------------------     // concat :: [[a]] -> [a]    const concat = xs => [].concat(...xs);      // nub :: [a] -> [a]    const nub = xs => [...new Set(xs)];      // sort :: Ord a => [a] -> [a]    const sort = xs =>        // An (ascending) sorted copy of xs.        xs.slice().sort();     return main();})();`
Output:
`[1, 3, 4, 5, 7, 8, 9]`

## jq

Works with: jq

Works with gojq, the Go implementation of jq

Assuming the input is a single array of arrays, we can simply chain the `add` and `unique` filters:

`jq -nc '[[5,1,3,8,9,4,8,7], [3,5,9,8,4], [1,3,7,9]] | add | unique'`
Output:
```[1,3,4,5,7,8,9]
```

If the arrays are presented individually in an external stream, we could use the `-s` command-line option.

Alternatively, here's a stream-oriented version of `add` that could be used:

`def add(s): reduce s as \$x (null; . + \$x);`

For example:

`jq -nc '    def add(s): reduce s as \$x (null; . + \$x);    add(inputs) | unique' <<< '[5,1,3,8,9,4,8,7] [3,5,9,8,4] [1,3,7,9]'`

## Julia

` julia> sort(union([5,1,3,8,9,4,8,7], [3,5,9,8,4], [1,3,7,9]))7-element Array{Int64,1}: 1 3 4 5 7 8 9 julia> sort(union([2, 3, 4], split("3.14 is not an integer", r"\s+")), lt=(x, y) -> "\$x" < "\$y")8-element Array{Any,1}: 2 3  "3.14" 4  "an"  "integer"  "is"  "not"  `

## Mathematica/Wolfram Language

`Union[{5, 1, 3, 8, 9, 4, 8, 7}, {3, 5, 9, 8, 4}, {1, 3, 7, 9}]`
Output:
`{1, 3, 4, 5, 7, 8, 9}`

## Nim

We could use a `HashSet` or an `IntSet` to deduplicate. We have rather chosen to use the procedure `deduplicate` from module `sequtils` applied to the sorted list.

`import algorithm, sequtils proc commonSortedList(list: openArray[seq[int]]): seq[int] =  sorted(concat(list)).deduplicate(true) echo commonSortedList([@[5,1,3,8,9,4,8,7], @[3,5,9,8,4], @[1,3,7,9]])`
Output:
`@[1, 3, 4, 5, 7, 8, 9]`

## Perl

`@c{@\$_}++ for [5,1,3,8,9,4,8,7], [3,5,9,8,4], [1,3,7,9];print join ' ', sort keys %c;@c{@\$_}++ for [qw<not all is integer ? is not ! 4.2>];print join ' ', sort keys %c;`
Output:
```1 3 4 5 7 8 9
! 1 3 4 4.2 5 7 8 9 ? all integer is not```

## Phix

Library: Phix/basics
```?unique(join({{5,1,3,8,9,4,8,7}, {3,5,9,8,4}, {1,3,7,9}, split("not everything is an integer")},{}))
```

Note the join(x,{}): the 2nd param is needed to prevent it putting 32 (ie the acsii code for a space) in the output.

Output:

(Unexpectedly rather Yoda-esque)

```{1,3,4,5,7,8,9,"an","everything","integer","is","not"}
```

## Python

`'''Common sorted list''' from itertools import chain  # ------------------------- TEST -------------------------# main :: IO ()def main():    '''Sorted union of lists'''     print(        sorted(nub(concat([            [5, 1, 3, 8, 9, 4, 8, 7],            [3, 5, 9, 8, 4],            [1, 3, 7, 9]        ])))    )  # ----------------------- GENERIC ------------------------ # concat :: [[a]] -> [a]# concat :: [String] -> Stringdef concat(xs):    '''The concatenation of all the elements in a list.    '''    return list(chain(*xs))  # nub :: [a] -> [a]def nub(xs):    '''A list containing the same elements as xs,       without duplicates, in the order of their       first occurrence.    '''    return list(dict.fromkeys(xs))  # MAIN ---if __name__ == '__main__':    main()`
Output:
`[1, 3, 4, 5, 7, 8, 9]`

## Quackery

`uniquewith` is defined at Remove duplicate elements#Quackery.

`  ' [ [ 5 1 3 8 9 4 8 7 ]      [ 3 5 9 8 4 ]      [ 1 3 7 9 ] ]   [] swap witheach [ witheach join ]  uniquewith > echo`
Output:
`[ 1 3 4 5 7 8 9 ]`

## Raku

`put sort keys [∪] [5,1,3,8,9,4,8,7], [3,5,9,8,4], [1,3,7,9];put sort keys [∪] [5,1,3,8,9,4,8,7], [3,5,9,8,4], [1,3,7,9], [<not everything is an integer so why not avoid special cases # ~ 23 4.2>];`
Output:
```1 3 4 5 7 8 9
# 1 3 4 4.2 5 7 8 9 23 an avoid cases everything integer is not so special why ~```

## REXX

`/*REXX pgm creates and displays a  common sorted list  of a specified collection of sets*/parse arg a                                      /*obtain optional arguments from the CL*/if a='' | a=","  then a= '[5,1,3,8,9,4,8,7]  [3,5,9,8,4]  [1,3,7,9]'     /*default sets.*/x= translate(a, ,'],[')                          /*extract elements from collection sets*/se= words(x)#= 0;            \$=                              /*#: number of unique elements; \$: list*/\$=                                               /*the list of common elements (so far).*/    do j=1  for se;  _= word(x, j)               /*traipse through all elements in sets.*/    if wordpos(_, \$)>0  then iterate             /*Is element in the new list? Yes, skip*/    \$= \$ _;   #= # + 1;    @.#= _                /*add to list; bump counter; assign──►@*/    end   /*j*/\$=call eSort #                                     /*use any short (small)  exchange sort.*/                 do k=1  for #;   \$= \$  @.k      /*rebuild the \$ list, it's been sorted.*/                 end   /*k*/ say 'the list of sorted common elements in all sets: ' "["translate(space(\$), ',', " ")']'exit 0                                           /*stick a fork in it,  we're all done. *//*──────────────────────────────────────────────────────────────────────────────────────*/eSort: procedure expose @.; arg h 1 z; do while h>1; h= h%2; do i=1  for z-h; j= i; k= h+i        do while @.k<@.j; [email protected].j; @.[email protected].k; @.k=t; if h>=j then leave; j=j-h; k=k-h; end;end        end;     return                          /*this sort was used 'cause of brevity.*/`
output   when using the default inputs:
```the list of sorted common elements in all sets:  [1,3,4,5,7,8,9]
```

## Ring

` nums = [[5,1,3,8,9,4,8,7],[3,5,9,8,4],[1,3,7,9]]sumNums = [] for n = 1 to len(nums)    for m = 1 to len(nums[n])        add(sumNums,nums[n][m])    nextnext sumNums = sort(sumNums)for n = len(sumNums) to 2 step -1    if sumNums[n] = sumNums[n-1]       del(sumNums,n)    oknext sumNums = sort(sumNums) see "common sorted list elements are: "showArray(sumNums) func showArray(array)     txt = ""     see "["     for n = 1 to len(array)         txt = txt + array[n] + ","     next     txt = left(txt,len(txt)-1)     txt = txt + "]"     see txt `
Output:
```common sorted list elements are: [1,3,4,5,7,8,9]
```

## Ruby

`nums = [5,1,3,8,9,4,8,7], [3,5,9,8,4], [1,3,7,9]p nums.inject(:+).sort.uniq   `
Output:
```[1, 3, 4, 5, 7, 8, 9]
```

## Wren

Library: Wren-seq
Library: Wren-sort
`import "/seq" for Lstimport "/sort" for Sort var distinctSortedUnion = Fn.new { |ll|     var res = ll.reduce([]) { |acc, l| acc + l }    res = Lst.distinct(res)    Sort.insertion(res)    return res} var ll = [[5, 1, 3, 8, 9, 4, 8, 7], [3, 5, 9, 8, 4], [1, 3, 7, 9]]System.print("Distinct sorted union of %(ll) is:")System.print(distinctSortedUnion.call(ll))`
Output:
```Distinct sorted union of [[5, 1, 3, 8, 9, 4, 8, 7], [3, 5, 9, 8, 4], [1, 3, 7, 9]] is:
[1, 3, 4, 5, 7, 8, 9]
```