{"entities":{"Q807015":{"pageid":808863,"ns":120,"title":"Item:Q807015","lastrevid":49518364,"modified":"2026-01-07T11:08:39Z","type":"item","id":"Q807015","labels":{"en":{"language":"en","value":"Parallel comparison merging of many-ordered lists"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 4205982"}},"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":"Q807015$019F9461-6BC0-4D9A-B771-EFC028F38F76","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"715394310a890496bbe4de7991619058a4613a55","datavalue":{"value":{"text":"Parallel comparison merging of many-ordered lists","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q807015$27503652-8DDA-4E80-AEA8-6A6F9BE9B5A3","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"8e1c804e8f5dc76799c467a2ebb88f941df8fca2","datavalue":{"value":"0729.68026","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q807015$E61B89C3-FEB2-45F6-B9B4-1B21C3E76E0A","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"c9ee7d80dd1e120d6b707083e01684ded7a63375","datavalue":{"value":"10.1016/0304-3975(91)90279-B","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q807015$98FCC6D7-7011-4E37-952B-EEDFA89F1EEF","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"f3c424cd94a60f9664f9fb69cc6027e75cc7ff3f","datavalue":{"value":{"entity-type":"item","numeric-id":123643,"id":"Q123643"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q807015$C9C85BBD-B7EC-4FD2-8557-46612BE239F7","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"391107ffc7a24346d69c573e292e4ff4587e3aaa","datavalue":{"value":{"time":"+1991-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":"Q807015$7FB941DB-F79A-4013-A9A3-5F14F683A723","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"4097b7aaad66e7ef7eadfa906abf4ced95734bbf","datavalue":{"value":"The paper deals with the analysis of the parallel algorithms for merging m disjoint ordered lists, each of size n/m. The problem is studied for the parallel comparison model with p parallel processors performing p comparisons in each time unit. Two theorems are proved. The first establishes the worst case time complexity for the given problem: \\(\\theta\\) ((log m)/log(1\\(+p/n)+\\log ((\\log n)/\\log (2+p/n))\\). This embodies the apriori known results for merging two equal lists \\((m=2)\\) and for sorting \\((m=n)\\). The second result shows that the average case complexity for the best randomized or deterministic parallel algorithm is the same, up to a constant factor, as the worst case complexity of the best deterministic one. This result is a generalization of a similar one given for sorting by the same author in a previous paper.","type":"string"},"datatype":"string"},"type":"statement","id":"Q807015$8258F123-0BA5-4877-910E-400F130E1AE9","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"fdd9498216d1fd2eff80e5a7d18782b649eb7b2f","datavalue":{"value":"68Q25","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q807015$A31CB566-FA39-4CA2-A002-13801D81232F","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"2b870cd98facc128596600f534ab32ee42736769","datavalue":{"value":"4205982","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q807015$28F97593-69CF-4D67-BB41-B8416EAAD8FC","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"d33669a46e6c8e8b36873d1f752821b7694a60c9","datavalue":{"value":"parallel algorithms","type":"string"},"datatype":"string"},"type":"statement","id":"Q807015$1254E2F0-6AC8-446F-8DFD-AFF9FB272F1C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"23cac259f02c32dba9b5ae35b9c89d13986c8417","datavalue":{"value":"merging ordered lists","type":"string"},"datatype":"string"},"type":"statement","id":"Q807015$FFC90ABF-E010-4181-AD1E-375DC1E6E87D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"de6e6ec99e87a64046813cb3b5f6f74ec4a4a7b2","datavalue":{"value":"average case complexity","type":"string"},"datatype":"string"},"type":"statement","id":"Q807015$81652CA1-02E6-4AC2-9A91-2A0342A8193E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"c15fa59b8f1ce206f81cf0de2875c3450ab5f6af","datavalue":{"value":"worst case complexity","type":"string"},"datatype":"string"},"type":"statement","id":"Q807015$09F58FC9-EBE8-44BF-B976-F3A502C98797","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"68814389157e3d8757e8eed17277cd2e82d90c5b","datavalue":{"value":{"entity-type":"item","numeric-id":526845,"id":"Q526845"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q807015$9F837935-A653-4048-90C5-26317F2D8089","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"e5adb2f5b9beef2201bef72e73c6f511c159db61","datavalue":{"value":{"entity-type":"item","numeric-id":493519,"id":"Q493519"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q807015$113ACB5D-BB87-402D-84ED-E916D6C03CBE","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":"Q807015$802DD262-27A3-45EA-974B-6FC91630B35A","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"f031a6aa561e20fa49312147fcef6d9e231ce948","datavalue":{"value":{"entity-type":"item","numeric-id":3802637,"id":"Q3802637"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q807015$99F009A7-EE9F-40B7-A4D7-4B06AF6893DF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"4f28ec91b2d54edc3fc4681626ee71f7102a2a9f","datavalue":{"value":{"entity-type":"item","numeric-id":3833631,"id":"Q3833631"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q807015$FCBA89A0-144A-48F3-8840-A761E279A2FB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"3289d5c8bdc255ddb24c9d379c1d7fcf656d76eb","datavalue":{"value":{"entity-type":"item","numeric-id":3805925,"id":"Q3805925"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q807015$6F9EA0CD-D1F2-4D91-BA53-7821BFA6C159","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":"Q807015$348E39DE-999A-4E71-BFFD-FB8C64F1573C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"633751807fff0d5b2a2a6c843fe9450f43f80eb5","datavalue":{"value":{"entity-type":"item","numeric-id":913517,"id":"Q913517"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q807015$63A1D008-9904-48C6-8FBC-9F6B1C18E5E7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"32b67dad640f548b66d589969379f540110243ee","datavalue":{"value":{"entity-type":"item","numeric-id":3801082,"id":"Q3801082"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q807015$14D1E54C-F776-4BD6-8AA6-57108694062B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"317a69c64db4a0e97be0d6d875029c549dbb18a4","datavalue":{"value":{"entity-type":"item","numeric-id":582080,"id":"Q582080"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q807015$609DED9F-A8D1-42CA-AD78-3B17C34FDF5A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"d333006ab5f5ba7661a2883dd9548d506c26947b","datavalue":{"value":{"entity-type":"item","numeric-id":1837535,"id":"Q1837535"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q807015$402D54F5-6B1C-4CC0-8330-0DF4BCEFC57E","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":"Q807015$639C1B4D-FAA5-4F69-BEA0-BA2E25C5AA73","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"a879a355ae8bb3c040f2bbf291ea6168340fae10","datavalue":{"value":{"entity-type":"item","numeric-id":3911406,"id":"Q3911406"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q807015$68594B96-6208-4DB0-BF57-275EDC9CB669","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"5ab54f9fde1cdfc86d62b3bd2c72ee9f0db9bf62","datavalue":{"value":{"entity-type":"item","numeric-id":3956411,"id":"Q3956411"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q807015$36CD8CCE-4E4C-4B5B-9E94-B8B0ADBB9BDE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"ecdacd7d8076e20fd3633d5d758e618af67b3432","datavalue":{"value":{"entity-type":"item","numeric-id":3038630,"id":"Q3038630"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q807015$ACD2F9C7-4D44-408E-9E8C-384BD08E891D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"5b90450ac678e8decbdb355819a362a9d83dbe48","datavalue":{"value":{"entity-type":"item","numeric-id":3323288,"id":"Q3323288"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q807015$541EDE5A-591C-4B54-8E17-EFC680923CB6","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"be20854391f682e3d34bfe4dd02ef650d80dfff9","datavalue":{"value":{"entity-type":"item","numeric-id":3801081,"id":"Q3801081"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q807015$2E715B2D-D132-4066-AF4C-84A18040118B","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":"Q807015$249837FA-5276-441A-B050-18B4FE3EFF9A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"105a42b9d963cd1fb6e3de311b73c6eb9ace9be3","datavalue":{"value":{"entity-type":"item","numeric-id":4069777,"id":"Q4069777"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q807015$1E38B12F-B6F0-407E-97D9-9D8F5B56FC92","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"a1b42e5866e3c65be83416ad499879c94baa889c","datavalue":{"value":{"entity-type":"item","numeric-id":3990098,"id":"Q3990098"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"c425a18d228ae5464a7f93a0d8cc2bd29da97ef0","datavalue":{"value":{"amount":"+0.8580430150032043","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":"Q807015$D1A69D22-9A3C-47FF-AF62-F4B30D62F06A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"336f270fcc9eef93f9e73c310fcf8e1464c77b9d","datavalue":{"value":{"entity-type":"item","numeric-id":4032936,"id":"Q4032936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"f6627ba566a0de852944e4826698c0f6733033fe","datavalue":{"value":{"amount":"+0.8534018993377686","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":"Q807015$70B8B18E-D55D-422F-B863-5F2B073F046F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"b08ac85dfc913a0f8355d3f5b4ebdf85abea76b6","datavalue":{"value":{"entity-type":"item","numeric-id":3719845,"id":"Q3719845"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"5dec0e5f397b7f8615df61ee3a1c9dd3296fa05a","datavalue":{"value":{"amount":"+0.8385666608810425","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":"Q807015$DC0CDEEE-CDDA-4805-AFCC-10B02ECD323B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"40168febbd608dd642f8d4f3cd95e4c1133d1554","datavalue":{"value":{"entity-type":"item","numeric-id":912634,"id":"Q912634"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"915bfaafe8931dc34feb017bb1a5d87d4902768b","datavalue":{"value":{"amount":"+0.8376615643501282","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":"Q807015$5F0C62BE-962F-4127-B862-DCB26CE0B272","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"d558c7a10b110b05b6d77afe8e7fc4fda2998dc3","datavalue":{"value":{"entity-type":"item","numeric-id":3142264,"id":"Q3142264"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"a93500c5d9f853a57c05aa480b1c9fd1e5039559","datavalue":{"value":{"amount":"+0.8286453485488892","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":"Q807015$1C903164-A0EE-42F7-9139-F1CB42ACC1AF","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:807015","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Publication:807015"}}}}}