{"entities":{"Q1379127":{"pageid":1389867,"ns":120,"title":"Item:Q1379127","lastrevid":67291170,"modified":"2026-04-12T16:38:35Z","type":"item","id":"Q1379127","labels":{"en":{"language":"en","value":"Periodic sorting using minimum delay, recursively constructed merging networks"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 1119070"}},"aliases":{},"claims":{"P31":[{"mainsnak":{"snaktype":"value","property":"P31","hash":"fd5912e4dab4b881a8eb0eb27e7893fef55176ad","datavalue":{"value":{"entity-type":"item","numeric-id":56887,"id":"Q56887"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1379127$37E0B19B-7AA7-48D3-BE19-A8E841E5572B","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"f288167e59b99c35e8be19e87ef1dc89a7e12fb9","datavalue":{"value":{"text":"Periodic sorting using minimum delay, recursively constructed merging networks","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1379127$EEE254F2-D0C9-48BA-A9CB-ACB319B8362E","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"fef727f451edca2f9c0b7dfc2475e56029cc603f","datavalue":{"value":"0884.68041","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1379127$9151D64B-D12B-4E5A-B338-2E4CD2F646DF","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"98974be3d76a16735c1235c5b39e5f8ca207c563","datavalue":{"value":{"entity-type":"item","numeric-id":585208,"id":"Q585208"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1379127$8813AE43-F799-42AE-8D57-CC633488EA48","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"06fdfc6a55ccd182e536d034b9a4565e196322b1","datavalue":{"value":{"entity-type":"item","numeric-id":698607,"id":"Q698607"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1379127$BF98D04F-BDDF-466A-941F-B995688DFC11","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"ebc7441ecfd9ecfa38d48ddc4b2adb39ac7d7000","datavalue":{"value":{"entity-type":"item","numeric-id":161296,"id":"Q161296"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1379127$123B97A3-C81D-4D5B-8D13-8D8D144914B6","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"335e18766e209cfa14c5766848f3c416f53156b7","datavalue":{"value":{"time":"+1998-02-18T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q1379127$C1C232CD-0D8C-496B-A8BB-E9E6A833B640","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"349f415c2190102e1e540c324f7615186e74db3d","datavalue":{"value":"https://eudml.org/doc/119227","type":"string"},"datatype":"url"},"type":"statement","id":"Q1379127$CC1D2665-93EF-4194-8A64-753FB8CE9690","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P205","hash":"e27799e4938a0a50a52b2cdaa1423ab64c4bc2f0","datavalue":{"value":"http://www.emis.de/journals/EJC/Volume_5/Abstracts/v5i1r5.html","type":"string"},"datatype":"url"},"type":"statement","id":"Q1379127$FCF61219-46DF-4FEB-879E-18D898DEB691","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"9288cbfffebfc826fa6e8ec38a87010568500346","datavalue":{"value":"Summary: Let \\(\\alpha\\) and \\(\\beta\\) be a partition of \\(\\{1,\\ldots,n\\}\\) into two blocks. A merging network is a network of comparators which allows as input arbitrary real numbers and has the property that, whenever the input sequence \\(x_1,x_2,\\ldots,x_n\\) is such that the subsequence in the positions \\(\\alpha\\) and the subsequence in the positions \\(\\beta\\) are each sorted, the output sequence will be sorted. We study the class of ``recursively constructed'' merging networks and characterize those with delay \\(\\lceil\\log_2 n\\rceil\\) (the best possible delay for all merging networks). When \\(n\\) is a power of 2, we show that at least \\(3^{n/2-1}\\) of these nets are log-periodic sorters; that is, they sort any input sequence after \\(\\log_2n\\) passes through the net. (Two of these have appeared previously in the literature.).","type":"string"},"datatype":"string"},"type":"statement","id":"Q1379127$1D98C3C2-1C00-4DB5-993F-36F642DF8344","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"3f97694d44af155a68434cb72eabc6a4d5dd5227","datavalue":{"value":"68P10","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1379127$2095F8D2-CD71-44ED-92F2-F1083D274866","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"24aafcf24a21bd70cd3b62d3f5f72a6d0d82d816","datavalue":{"value":"68-02","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1379127$93A1CC92-E19C-49D3-9381-4A41D171E29F","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"851b118e0cc1bc51c6646b51986bf30dba6f9045","datavalue":{"value":"1119070","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1379127$8E52AE0F-4BC0-46C1-8B24-0EEF088DCACF","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"117244acb09ea9f1619f5825cbe19a114d67d9d6","datavalue":{"value":"merging network","type":"string"},"datatype":"string"},"type":"statement","id":"Q1379127$9AE8F16C-5ACC-4D23-9E35-3A639D80AF24","rank":"normal"}],"P1460":[{"mainsnak":{"snaktype":"value","property":"P1460","hash":"57f7fea50d2ce1b39b695c4a1313582eed405e38","datavalue":{"value":{"entity-type":"item","numeric-id":5976449,"id":"Q5976449"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1379127$1C2D1839-1D6D-4523-A362-4A4044D8CDC4","rank":"normal"}],"P1633":[{"mainsnak":{"snaktype":"value","property":"P1633","hash":"856a9f5f5dd7dc042020d50b9820e6242aa3447b","datavalue":{"value":"bafkreihrfnf4ptphfalyltirrov6fbvv2fctbl3syapwfqcy7qcay7432e","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1379127$BA2925B9-F07D-4A36-93E5-ECC2F443D0EB","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"12a35889fda4d5726253602073623f2aa8ce660e","datavalue":{"value":{"entity-type":"item","numeric-id":2629229,"id":"Q2629229"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"35e1afc0fc0181a62d1355290cff5d5cf010399a","datavalue":{"value":{"amount":"+0.8618519306182861","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"a327a09ea0305e98d5cf33bd4036320e19f2aed0","datavalue":{"value":{"entity-type":"item","numeric-id":6821328,"id":"Q6821328"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1379127$9BEFC370-7C36-4716-95DC-A384B6447175","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"8869b6b363fd39725553119ae5a2562e74bc5b05","datavalue":{"value":{"entity-type":"item","numeric-id":6487453,"id":"Q6487453"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"741850b4163b6cb3b0dc39077b85c7658d469e09","datavalue":{"value":{"amount":"+0.8607102632522583","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"a327a09ea0305e98d5cf33bd4036320e19f2aed0","datavalue":{"value":{"entity-type":"item","numeric-id":6821328,"id":"Q6821328"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1379127$5AB715EF-C91F-4866-AE75-64894FCA7113","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"97551929d3d7ea377def61ff339b64a43e730036","datavalue":{"value":{"entity-type":"item","numeric-id":1271276,"id":"Q1271276"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"df4a69d938ee074ba1a1bfee2f00c3dfcff040f9","datavalue":{"value":{"amount":"+0.8592965602874756","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"a327a09ea0305e98d5cf33bd4036320e19f2aed0","datavalue":{"value":{"entity-type":"item","numeric-id":6821328,"id":"Q6821328"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1379127$74E8B335-35F3-451E-801E-D0001E6F0537","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"ac0f2063bf5f0f72552231e343e82d6dd2c40f46","datavalue":{"value":{"entity-type":"item","numeric-id":1273856,"id":"Q1273856"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"53f8e2c5170472f64aa63ec194d4877fdc49cbf3","datavalue":{"value":{"amount":"+0.8431885242462158","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"a327a09ea0305e98d5cf33bd4036320e19f2aed0","datavalue":{"value":{"entity-type":"item","numeric-id":6821328,"id":"Q6821328"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1379127$F218439C-FBAE-44E5-8D6B-24F1DC8D6F27","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Periodic sorting using minimum delay, recursively constructed merging networks","badges":[]}}}}}