{"entities":{"Q805234":{"pageid":807082,"ns":120,"title":"Item:Q805234","lastrevid":64472181,"modified":"2026-04-11T20:06:33Z","type":"item","id":"Q805234","labels":{"en":{"language":"en","value":"On parallel integer sorting"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 4203720"}},"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":"Q805234$CE56FEF7-C384-4756-864C-E7DBC62F513C","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"dfa88dcc15668f1cc74a84a858412f3293ef831d","datavalue":{"value":{"text":"On parallel integer sorting","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q805234$A6500A42-FC4A-402B-A588-92B4DD669142","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"f7bdf7d093dd89df24d60f119ab9c14b7ab289b2","datavalue":{"value":"0728.68066","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q805234$213EBF4C-FBFA-44B0-A819-3E64347712D0","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"a0fb01fc839a7242bd937a2cb3dce88d1efa4703","datavalue":{"value":"10.1007/BF01178563","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q805234$60117DE1-BDAD-4C2E-8A59-45DA61D7DA83","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"ada2fa77d7e2c64389aeedcd6a72d8decb4910cc","datavalue":{"value":{"entity-type":"item","numeric-id":293337,"id":"Q293337"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q805234$71416677-B807-4175-8940-6F3F5F8EB658","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"5bc7722cfcbf8d4f5c475e825f9c5b9c9a03de5a","datavalue":{"value":{"entity-type":"item","numeric-id":315535,"id":"Q315535"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q805234$4BB8618A-045B-4747-A03B-50D2F84848AF","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"7d0f02e85530cd06ceb2c58a40dc9c2e0258e194","datavalue":{"value":{"entity-type":"item","numeric-id":161641,"id":"Q161641"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q805234$66594488-23BB-4D7F-ABFB-FCC88DDB561A","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"ebf2f83ceb66feb8490ae2b363c9cada085a3535","datavalue":{"value":{"time":"+1992-00-00T00:00:00Z","timezone":0,"before":0,"after":0,"precision":9,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q805234$4E186AEF-4494-4003-B08D-A914E1B26C86","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"f16907c010b82dffe058fcd55205ba94fe609f49","datavalue":{"value":"We present an optimal algorithm for sorting n integers in the range \\([1,n^ c]\\) (for any constant c) for the EREW PRAM model where the word length is \\(n^{\\epsilon}\\), for any \\(\\epsilon >0\\). Using this algorithm, the best known upper bound for integer sorting on the (O(log n) word length) EREW PRAM model is improved. In addition, a novel parallel range reduction algorithm which results in a near optimal randomized integer sorting algorithm is presented. For the case when the keys are uniformly distributed integers in an arbitrary range, we give an algorithm whose expected running time is optimal.","type":"string"},"datatype":"string"},"type":"statement","id":"Q805234$B6FC5A11-4ABB-4EB2-9246-B3F908BFA1AD","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"b65efe51b183d0f4a672427b8171cd1e14211cba","datavalue":{"value":"68W15","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q805234$3B52E5F5-95DB-4DF0-AFDC-EDCB7A4F406E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"3f97694d44af155a68434cb72eabc6a4d5dd5227","datavalue":{"value":"68P10","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q805234$B2E3E3F4-81E9-4BAA-BDB1-295ADA509C5A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"fdd9498216d1fd2eff80e5a7d18782b649eb7b2f","datavalue":{"value":"68Q25","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q805234$208439F9-728A-4E38-8FC1-AC2B1523C693","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"22c2ed2f66847d90501b665adac4ca2491698bdf","datavalue":{"value":"4203720","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q805234$8557A980-5C29-4D44-A526-BF9A843FD33D","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"fc00012563a75ed0c7975e9c32d5f2d16f0982e3","datavalue":{"value":"optimal algorithm","type":"string"},"datatype":"string"},"type":"statement","id":"Q805234$23D75E24-AF57-4A2F-A8F3-560FF04F66F8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"4f0de1c9f116b71d20e00b93e07300eed544fdd8","datavalue":{"value":"EREW PRAM","type":"string"},"datatype":"string"},"type":"statement","id":"Q805234$D24DF74A-1A9A-469C-8013-8A8AB5935E2B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"d7a95ceb6d67e935db7a76acd724a8b7ba5da3bf","datavalue":{"value":"integer sorting","type":"string"},"datatype":"string"},"type":"statement","id":"Q805234$77334B37-CAE3-4090-814D-DE0B174C8182","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"ad7010e429378b2130939bcc2d60787717543ea8","datavalue":{"value":"optimal randomized integer sorting","type":"string"},"datatype":"string"},"type":"statement","id":"Q805234$961A6CA2-1544-4D54-97D4-506B4AB46954","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":"Q805234$64015C0A-F238-473E-A387-36909044E437","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"340ea97c0f2f383d364057042ebc9f9438fcc85a","datavalue":{"value":{"entity-type":"item","numeric-id":4091421,"id":"Q4091421"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q805234$663BCD47-8989-40F1-A568-8022F36257D9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"7b44ed555aed1fbc544de1802074fd0df13fb2c0","datavalue":{"value":{"entity-type":"item","numeric-id":1056541,"id":"Q1056541"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q805234$95586644-AAAA-417D-8C34-2459838ADA16","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"83c6293f25e8bc7e1747aa6978fc2fd52b5104b6","datavalue":{"value":{"entity-type":"item","numeric-id":1141153,"id":"Q1141153"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q805234$A267AF48-50DD-4506-8F3F-7A34871FB546","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"77d6452e54e5e6983bfa6dba10e55824db2fd929","datavalue":{"value":{"entity-type":"item","numeric-id":5814290,"id":"Q5814290"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q805234$85663D64-EF76-442F-8056-3D573DB87289","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"07084f93b98d5e74727a61f004966357d26a22db","datavalue":{"value":{"entity-type":"item","numeric-id":1263965,"id":"Q1263965"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q805234$DB2FAAE7-B64A-4195-B65F-0E856BBB521D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"bba9e98d83fb097641689563c120aebf958873f5","datavalue":{"value":{"entity-type":"item","numeric-id":3796769,"id":"Q3796769"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q805234$EA1D4118-1926-499E-8618-EE0B5D68524D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"d6678f06a75d43bea3eef6b354d6f3a891778147","datavalue":{"value":{"entity-type":"item","numeric-id":1108805,"id":"Q1108805"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q805234$3332715C-1D98-4BEF-9E70-232D40F99BA9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"f1c5a96890a21e10169edc66df7fd407f84f079a","datavalue":{"value":{"entity-type":"item","numeric-id":1825647,"id":"Q1825647"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q805234$7480676F-8309-4A4F-B778-E11E945BF394","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"e707cd23efd0528805ea80e15df034ae81af633a","datavalue":{"value":{"entity-type":"item","numeric-id":1098305,"id":"Q1098305"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q805234$E0EE4A5F-0B09-4119-B899-832A97263568","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"dd5f640ca9f6b16931310ffe7ccd1a2d8f63de02","datavalue":{"value":{"entity-type":"item","numeric-id":1123628,"id":"Q1123628"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q805234$88DFB293-B362-434F-802A-7A3DDFD0FCA2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"512895b5566cdd356d481036e29910ba40af39d6","datavalue":{"value":{"entity-type":"item","numeric-id":789897,"id":"Q789897"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q805234$8F48F91B-64A4-4F0F-AAEF-B4AEE96B8206","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"ff81489e80366438468bf6dfe10c7a159bc3ea8c","datavalue":{"value":{"entity-type":"item","numeric-id":4057549,"id":"Q4057549"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q805234$7B91809A-EF74-403C-8DFA-C4D2D373D541","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"466da13790de3cc5dd610755dd40b723890854f6","datavalue":{"value":{"entity-type":"item","numeric-id":1262781,"id":"Q1262781"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q805234$4DDE9E67-9EBD-4A31-A9C3-65463F9DD673","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"508894c78bd2770d073dbe57a0316a7e71f6bc30","datavalue":{"value":{"entity-type":"item","numeric-id":3890136,"id":"Q3890136"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q805234$F62F9F9F-B17A-42C6-919B-6B80916C6CF1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"24ffb622144ae8afe26205a9b88cdf84573c2b54","datavalue":{"value":{"entity-type":"item","numeric-id":5557495,"id":"Q5557495"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q805234$79A0F999-1E91-4683-890D-F96A1C0D35A7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"9387bbd38b0874a230355988a020913f3259fce1","datavalue":{"value":{"entity-type":"item","numeric-id":3219751,"id":"Q3219751"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q805234$FDFDC0FA-4F27-49C2-9A75-226308D2819C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"a44b1a67f272e43c205ead148dcbb6bc6f2c307b","datavalue":{"value":{"entity-type":"item","numeric-id":4729356,"id":"Q4729356"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q805234$79CFCEE9-D421-437F-B6ED-8EFF34F1226E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"ae6af26f7dce6f438ad391d3123d3e7ba534c4a4","datavalue":{"value":{"entity-type":"item","numeric-id":3700837,"id":"Q3700837"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q805234$23CAF964-249D-4BFD-B81E-5254B73FD51B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"06b820d7730c4483ffdeaf5f1bb9567aad23b088","datavalue":{"value":{"entity-type":"item","numeric-id":3906428,"id":"Q3906428"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q805234$7C3D3941-74BE-42BC-8C63-07AA2DF687D3","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"f4c0c850a82c765897db7ddacfdcfe4f81e5ce11","datavalue":{"value":{"entity-type":"item","numeric-id":1362905,"id":"Q1362905"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"90e72dea2968a83568d1f9b185f9ff665456af1a","datavalue":{"value":{"amount":"+0.9281414151191713","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":"Q805234$53A112D8-136A-4432-A268-69C1570654BF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"46e1400426afefd2d0c5026edfecd7b8d109dced","datavalue":{"value":{"entity-type":"item","numeric-id":1346223,"id":"Q1346223"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"cd4d2f6680596aa19605be5a7c5c68ced6bdf7f5","datavalue":{"value":{"amount":"+0.9219953417778016","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":"Q805234$2B31110D-D9B5-487C-B687-51FC92E38FFC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"f74c7593af031d0c07234ac77feaa12ecf00666e","datavalue":{"value":{"entity-type":"item","numeric-id":4252316,"id":"Q4252316"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"1ee4fe4cba6ab7547eac60bcbb43e81f493d1ca7","datavalue":{"value":{"amount":"+0.9202277660369872","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":"Q805234$53EE5224-7CB1-47C7-8017-99811411909A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"c9362de7ec8cbd9efa7ce3a2d09a8c5975fd0e65","datavalue":{"value":{"entity-type":"item","numeric-id":4016534,"id":"Q4016534"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"a37096fffb347f5c27c2a1fe407b388c799f32cd","datavalue":{"value":{"amount":"+0.9188952445983888","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":"Q805234$1BDA70CF-A5A0-4305-A155-2B8DF1DCC1F8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"4e48844608ad0caa28ce68717228ab9120ff8b31","datavalue":{"value":{"entity-type":"item","numeric-id":4763434,"id":"Q4763434"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"08f9d35cc3bc581459207b1e8452dbd6530b16b5","datavalue":{"value":{"amount":"+0.9174448847770692","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":"Q805234$86A31145-9DC5-4BAB-8FEE-50BB77EB28C8","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"On parallel integer sorting","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/On_parallel_integer_sorting"}}}}}