{"entities":{"Q688438":{"pageid":690287,"ns":120,"title":"Item:Q688438","lastrevid":47204236,"modified":"2026-01-01T00:10:13Z","type":"item","id":"Q688438","labels":{"en":{"language":"en","value":"Integer sorting on a mesh-connected array of processors"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 444828"}},"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":"Q688438$E6A5A72D-CB45-4EF8-894E-619CBD119528","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"6154790f9550d37272e354b1cdac1654b6b47cc7","datavalue":{"value":{"text":"Integer sorting on a mesh-connected array of processors","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q688438$BF110558-BA18-4583-8441-FB5C9E501987","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"8983fe50a80e9e25b8d1ad4eeb62f8e6a63002b6","datavalue":{"value":"0801.68069","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q688438$B8DD625E-A459-4BF1-B02B-DBF0020B3C00","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"66bb3e0a4bc962d74e76bd72a0b3ce177a1d75da","datavalue":{"value":"10.1016/0020-0190(93)90073-I","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q688438$F74ED65A-2DB8-4058-AFFC-AAB44A3FB126","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"3510588941215065bc6a9d8f23e378fe2770ea1f","datavalue":{"value":{"entity-type":"item","numeric-id":215101,"id":"Q215101"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q688438$3AB96C7E-6729-42E4-A057-66450BBFDA68","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"52fa7d44b58d0511cb8993765bd916aef86052d8","datavalue":{"value":{"entity-type":"item","numeric-id":63092,"id":"Q63092"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q688438$A3E5A5A5-461A-4107-A549-C30744C1656D","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"92112234a474f78049341bfb55637019f67e54ac","datavalue":{"value":{"time":"+1993-12-20T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q688438$887178BD-2EFB-4735-AE57-9B1DD5F7D202","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"93a6600c90e0e054c0de1177ef7464a80895310c","datavalue":{"value":"The problem of sorting is of fundamental importance in computing. In sequential models of computation the difference between sorting general inputs and sorting integers in a fixed range has been well established. In a model where only comparisons between inputs are allowed a lower bound of \\(\\Omega(N\\log N)\\) for sorting \\(N\\) inputs is well known. However if we know the inputs fall in a polynomial-size range, an algorithm with complexity \\(O(N)\\) is possible. In this paper we study the effect of limiting the inputs to be integers in the range \\([1\\ldots N]\\) in the case of sorting \\(N=n^ 2\\) inputs on an \\(n\\times n\\) mesh-connected array of processors.","type":"string"},"datatype":"string"},"type":"statement","id":"Q688438$425D522E-896C-46AF-8F64-12A379B94174","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"b65efe51b183d0f4a672427b8171cd1e14211cba","datavalue":{"value":"68W15","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q688438$23A974C2-9EED-4513-98ED-C690838876DC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"3f97694d44af155a68434cb72eabc6a4d5dd5227","datavalue":{"value":"68P10","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q688438$9E2BBE97-AAA7-4F50-B90B-49E8F5C3C547","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"bd40da6adb41637448d86bbc9ae0feb2350f5ff3","datavalue":{"value":"444828","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q688438$73BECFF2-4B05-4E28-8405-296E2E4CC8A6","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"d33669a46e6c8e8b36873d1f752821b7694a60c9","datavalue":{"value":"parallel algorithms","type":"string"},"datatype":"string"},"type":"statement","id":"Q688438$6370D89D-647C-4D69-8434-F9DD199111C4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"d7a95ceb6d67e935db7a76acd724a8b7ba5da3bf","datavalue":{"value":"integer sorting","type":"string"},"datatype":"string"},"type":"statement","id":"Q688438$31636C1D-E514-4FEA-B90D-332EBF38CEE5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"a4368d84c0dc2e94c7938147c8c2415c696a5830","datavalue":{"value":"connected array","type":"string"},"datatype":"string"},"type":"statement","id":"Q688438$A37BACE0-8E78-4361-9447-72EAFAF5050A","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":"Q688438$EB379F55-8F71-4AD9-9DA0-E7AFDAF0D412","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"dd3a7cfeece8562a9ac87120b107e2b528967937","datavalue":{"value":{"entity-type":"item","numeric-id":4773298,"id":"Q4773298"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q688438$963E543C-C2CF-4EB7-8C93-EA0328512016","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"5b246cab2d494a33065b1df5ef36c7e813de2046","datavalue":{"value":{"entity-type":"item","numeric-id":1091826,"id":"Q1091826"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q688438$6CE3C4E7-68A7-4E60-9448-3D8A496301D9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"b8f18ea1af35e16f8b078e128f38839dcba5c2a1","datavalue":{"value":{"entity-type":"item","numeric-id":4120129,"id":"Q4120129"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q688438$769E1AE1-B05B-40AA-A326-BB0EB7D376D6","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"fef822135fd12cd5fa0f36b8c8493aa19652eeb8","datavalue":{"value":{"entity-type":"item","numeric-id":1091826,"id":"Q1091826"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"f67aa88e5da3018804fe65e54d55a3babdbdeea9","datavalue":{"value":{"amount":"+0.8346425294876099","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":"Q688438$C831A5FB-05D3-4888-A603-D54E95CBA786","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"b16ff9a0a12838f29eb86800a53553fb5104d4d4","datavalue":{"value":{"entity-type":"item","numeric-id":3727395,"id":"Q3727395"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"2d446361a3eec60209abfc0973ac6934034fafc5","datavalue":{"value":{"amount":"+0.8335250616073608","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":"Q688438$D3995FA2-CC3D-4E0C-B1F5-4238BB763DF3","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"fa120c7e9f4e63a9eb612e873ff0baa1128ce76e","datavalue":{"value":{"entity-type":"item","numeric-id":3484347,"id":"Q3484347"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"2f835c08a76bb1dca1d53f62bf23886453b0ebdb","datavalue":{"value":{"amount":"+0.8248322606086731","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":"Q688438$1D834951-3729-4173-B837-7AC4460A36A8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"ecf07df8ee8f20204fc2496e72a8e6ef76dbf218","datavalue":{"value":{"entity-type":"item","numeric-id":3774969,"id":"Q3774969"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"482b251893095a4ed1b43a1b2b990cee551fddc4","datavalue":{"value":{"amount":"+0.8155862092971802","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":"Q688438$CFF66D9C-EDA6-4B7E-B04C-4AC5E36F24DB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"c1698e1d6268df8fdaddeb160e5dc28c20bc1f43","datavalue":{"value":{"entity-type":"item","numeric-id":1112618,"id":"Q1112618"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"7f7bf19ffb37f973fa3d000378e05b8018e5af14","datavalue":{"value":{"amount":"+0.8153502941131592","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":"Q688438$FA32BD13-0CC1-4D63-9797-F728329D2F56","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:688438","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Publication:688438"}}}}}