{"entities":{"Q1199552":{"pageid":1210301,"ns":120,"title":"Item:Q1199552","lastrevid":66465135,"modified":"2026-04-12T10:15:40Z","type":"item","id":"Q1199552","labels":{"en":{"language":"en","value":"An efficient parallel sorting algorithm"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 94472"}},"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":"Q1199552$08330F5F-1346-4A83-933D-B3125339BA5A","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"727d1ee5462f3c3847f3d190be34662f6d43682c","datavalue":{"value":{"text":"An efficient parallel sorting algorithm","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1199552$AE16C80F-E3B1-483C-8204-6A3DD4210D69","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"e25579956c297b5470cf8943873fdced3c44ded8","datavalue":{"value":"0753.68033","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1199552$8C70DE1D-E735-4354-B9BC-69C495C6CFC4","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"466b917155c8454a2de6b5335c76b6f2eafb5269","datavalue":{"value":"10.1016/0020-0190(92)90004-F","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1199552$4877FE12-CA93-4768-881D-A414EC97F66C","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"2a409663a3ee3c4a0037d985c389e6c97b692fd4","datavalue":{"value":{"entity-type":"item","numeric-id":308838,"id":"Q308838"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1199552$6CEF873C-2ECF-40AA-88E2-35484FFA6ECC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"518aaa18fce13f6b6dba89b88dd5dddecf847e0f","datavalue":{"value":{"entity-type":"item","numeric-id":672658,"id":"Q672658"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1199552$B416F6AE-BD4C-49DE-A0AE-4B9706B6D628","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":"Q1199552$46338AF5-B75F-48ED-AB7E-A9EE5DF3A3DC","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"be1a65edbb43ce1fc59464f99e70afbd93e8e2a0","datavalue":{"value":{"time":"+1993-01-16T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q1199552$9948E64D-E484-4D39-8DAD-AC3761EEE004","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"f4c7fca5ee1c1d41eaaa58253f2a4122b8b60b9a","datavalue":{"value":"We consider the merge-based sorting on the EREW PRAM multiprocessor with private caches. We propose a parallel sorting algorithm that achieves linear speedup in both the number of comparisons and the number of data accesses, using a novel partition algorithm which splits an arbitrary number of sorted runs among all the processors evenly, independent of the sort-key value. The percentile point for each sorted run is found efficiently and only one merge pass is required. The processing and access costs are \\(O(t_ p((N/P)\\log N+P\\log(N/(2P))))\\) and \\(O(t_ a((N/P)(\\log(NM/P)/\\log M)+P\\log(N/(2P))))\\), where \\(N\\) is the number of data elements, \\(P\\) is the number of processors, \\(M\\) is the size of the cache, \\(t_ p\\) is the time needed to execute an instruction using cache memory and \\(t_ a\\) is the time needed for a data access from shared memory.","type":"string"},"datatype":"string"},"type":"statement","id":"Q1199552$805A4647-E043-4277-A250-BDAFE145EE78","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"3f97694d44af155a68434cb72eabc6a4d5dd5227","datavalue":{"value":"68P10","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1199552$01C38597-4BCE-4018-8B10-52FF82EFE72E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"b65efe51b183d0f4a672427b8171cd1e14211cba","datavalue":{"value":"68W15","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1199552$E4E447CD-EFBE-45DB-8AF5-CD4A098223CD","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"fdd9498216d1fd2eff80e5a7d18782b649eb7b2f","datavalue":{"value":"68Q25","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1199552$02E6CC6A-3F1A-4904-BB5E-0C8A9E7AA80D","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"d77a416ddd22aad4d4b77f2c802174ac671b9294","datavalue":{"value":"94472","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1199552$97B876C9-0C02-4CAF-84CC-8C11E196B7D6","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"ee4333081aeed9cb416827114fc33bcfc3b51deb","datavalue":{"value":"partitioning","type":"string"},"datatype":"string"},"type":"statement","id":"Q1199552$C3FB19CA-4991-4717-92EF-E7B2CB8024C0","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"1c2429349fe6ad34348df532161c2c6d4e44d116","datavalue":{"value":"merging","type":"string"},"datatype":"string"},"type":"statement","id":"Q1199552$9575B892-9014-4F3A-AE3F-53AB9A808251","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"4f0de1c9f116b71d20e00b93e07300eed544fdd8","datavalue":{"value":"EREW PRAM","type":"string"},"datatype":"string"},"type":"statement","id":"Q1199552$A3D7280E-024F-41BD-8ECD-CDEBD252AB0C","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":"Q1199552$9FB33BEC-535C-4E1B-AADE-5C8F41E5D5C8","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"10cbec46e97dc9a5d6f2daec595161628d2f018c","datavalue":{"value":{"entity-type":"item","numeric-id":1824383,"id":"Q1824383"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1199552$176320DA-C774-4868-BDC2-75EE92D73924","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"09abae86cc1ed38b7527e20b0a54f0f51ad25c1f","datavalue":{"value":{"entity-type":"item","numeric-id":1099951,"id":"Q1099951"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1199552$74963CC5-567A-44BD-A138-50E4195366BD","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"938c5099f33f18a407cb379fd5495916fbc0113b","datavalue":{"value":"https://doi.org/10.1016/0020-0190(92)90004-f","type":"string"},"datatype":"url"},"type":"statement","id":"Q1199552$53A4A48F-260A-4C6C-A4D6-ED80918BD261","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"7d719d730d90be7ddebba8fbb1b1d96d32e34faa","datavalue":{"value":"W2321698191","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1199552$0003C544-ADED-4E70-A2E6-820AFFE81F52","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"1bfa8bd522d099b903644ee029e8dbf35f552263","datavalue":{"value":{"entity-type":"item","numeric-id":1185926,"id":"Q1185926"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"54840af4595ac9d6dc7086d68287573e06c0ec06","datavalue":{"value":{"amount":"+0.8574866056442261","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":"Q1199552$E6446AA0-4AFF-4A44-81F5-84DF048F4FFB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"f4046bf6279a0256c5a330ab101fbdb5adfa9d0a","datavalue":{"value":{"entity-type":"item","numeric-id":4785624,"id":"Q4785624"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"3ab736c728beeb67c7334d27560fc2b32a002702","datavalue":{"value":{"amount":"+0.8570261597633362","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":"Q1199552$0F131188-3FB6-44A0-A081-B9277756F25A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"fbf4de38a0361b30916ed5a285a4a704acb68d96","datavalue":{"value":{"entity-type":"item","numeric-id":1200122,"id":"Q1200122"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"e31c3f471b69dab7b682df4be15003cce5357673","datavalue":{"value":{"amount":"+0.8455366492271423","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":"Q1199552$7DAF5FEC-6B5F-4224-AAE7-3F3EDA189868","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"6b43b0e32becc6b9e24b912c0789360df5a66e16","datavalue":{"value":{"entity-type":"item","numeric-id":3796769,"id":"Q3796769"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"dccd9a9aef3bc9b0111fdd3a497d24083777a4ef","datavalue":{"value":{"amount":"+0.8437739610671997","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":"Q1199552$70739090-A28A-4B86-8BFD-89A071D6F7D7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"2b5742b8172c679bf7ef2f563100951b3c8ff014","datavalue":{"value":{"entity-type":"item","numeric-id":3814825,"id":"Q3814825"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"83409b43715b7db2088fc9205aed4a61b3519d93","datavalue":{"value":{"amount":"+0.8356019258499146","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":"Q1199552$A60D8926-D84A-4C51-A0EE-0E416ADA1D6B","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"An efficient parallel sorting algorithm","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/An_efficient_parallel_sorting_algorithm"}}}}}