{"entities":{"Q533870":{"pageid":535637,"ns":120,"title":"Item:Q533870","lastrevid":62552703,"modified":"2026-04-11T06:52:12Z","type":"item","id":"Q533870","labels":{"en":{"language":"en","value":"Bitonic sorters of minimal depth"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 5886211"}},"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":"Q533870$F8371CA2-26D5-48B8-84F3-D4249780F9E8","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"8566be3cf0eecadc9458240b5039ebeb3c431e96","datavalue":{"value":{"text":"Bitonic sorters of minimal depth","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q533870$6007043E-7375-4123-9B8D-6605CB9B44F5","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"3269af481f8a9970e9f2f7c1fe3a639edd07534d","datavalue":{"value":"1233.68029","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q533870$FC8EED59-CEFE-4A3E-84EE-EF0234600765","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"276cca11df30a1b0563d815677ea07e56e2fa97d","datavalue":{"value":{"entity-type":"item","numeric-id":533868,"id":"Q533868"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q533870$F8BF405C-5AFC-4DDD-9259-CD1D4597440D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"f227a94652293a56daa501bf5619798fc97d2b3e","datavalue":{"value":{"entity-type":"item","numeric-id":533869,"id":"Q533869"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q533870$65911929-13B2-4D6A-B9A8-073D37B6A180","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":"Q533870$47264882-A964-4EEE-81E0-5871C4E913DF","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"6355dd651d7e8925edcf5ba080dbea252734508c","datavalue":{"value":{"time":"+2011-05-10T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q533870$F42AAF16-F41F-4A54-9395-B03BB5031B67","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"6a008fdacc0c9e8ed2dc758f60fc2d96b7755da2","datavalue":{"value":"The well-written paper deals with the problem of constructing (acyclic) comparator networks of minimal depth for sorting bitonic input sequences. A bitonic sequence (of \\(n\\) keys) is defined by the authors as a rotation of a concatenation of two sequences -- an ascending sequence followed by a descending one. For sorting bitonic sequences of \\(n\\) keys the authors construct a network of comparators (i.e. combinational devices sorting two elements) with depth equal to \\(\\lceil\\log(n)\\rceil+1\\). This is an improvement of the previous known result, where such a network was constructed only for sequences with the number of keys equal to a power of two. The network is presented by the authors in the clever graphical representation.   In the proof the authors use their own concept of weakly symmetric networks, where the input-to-output transformation is symmetric. The only (minor) defect is that the authors refer to the technical report (probably unpublished paper) where they proved the key lower bound on the depth of bitonic sorters.","type":"string"},"datatype":"string"},"type":"statement","id":"Q533870$575BA133-2CB0-4D49-A71E-CD475A20C2AE","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"31e53858502c36bbebbef6741b4a5445fe12585e","datavalue":{"value":{"entity-type":"item","numeric-id":590282,"id":"Q590282"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q533870$9AC3E59B-D6D7-4CD6-97FA-C1B6B01F52E6","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"cd80e9ade304e6b9b43fd50d0c3436276c3c217e","datavalue":{"value":"68M07","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q533870$35B6FCD7-E9A5-4FA6-BE47-EE63ABDE3BE9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"3f97694d44af155a68434cb72eabc6a4d5dd5227","datavalue":{"value":"68P10","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q533870$1BD6A2DF-9B6C-4B68-990B-AD700D5556A9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"4a5372688a0d668805df5d9ffd1da58833a0f595","datavalue":{"value":"68R05","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q533870$877CBC14-0ED0-4291-BFA4-4A12BD2F98B2","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"513b142a881d2b9bc95ed3f07a577b140f32384f","datavalue":{"value":"5886211","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q533870$6B50D285-4AB7-4086-9669-86324374D97C","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"2059b53729ebfc0a506d814274b62d5a08ebda59","datavalue":{"value":"computer system organization","type":"string"},"datatype":"string"},"type":"statement","id":"Q533870$00466331-8D72-4AA2-B5A4-F729A0365C2E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"d607627523840bd0bf4407097f29a3a99ef4a0a8","datavalue":{"value":"algorithms","type":"string"},"datatype":"string"},"type":"statement","id":"Q533870$06B14639-0CC2-43C4-A61D-41048927E1F0","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"22b9b22044b92ef422314b33354a4ac45000b73b","datavalue":{"value":"searching and sorting","type":"string"},"datatype":"string"},"type":"statement","id":"Q533870$C8C21BFB-34D0-40CA-9D08-0D749FD02641","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":"Q533870$6A1042F4-A75B-43CD-82A1-CF5173D49F2B","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"cd521719dfc6145b46495704fc362a6753497531","datavalue":{"value":"https://doi.org/10.1016/j.tcs.2011.01.006","type":"string"},"datatype":"url"},"type":"statement","id":"Q533870$46E8BDFB-9B71-48D2-908E-70A6C7BE0A31","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"3608cf851ba8680d996a345e77a53b020bbb8c85","datavalue":{"value":"W2075192920","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q533870$71576AF3-5F0E-43BF-B759-9A76617C13EE","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"e2924b760b12273871e2484a086304f8fdaa7f63","datavalue":{"value":{"entity-type":"item","numeric-id":1008736,"id":"Q1008736"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q533870$16D99962-653E-4D14-BED4-097B029ED29A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"0252db8f91fc184001751f0eeb3107ef96bd911b","datavalue":{"value":{"entity-type":"item","numeric-id":4349924,"id":"Q4349924"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q533870$DE4B5794-C394-4736-9AC2-9A4569DC5618","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"1b79b9186fe92c4f81d60678b527447e41a845da","datavalue":{"value":{"entity-type":"item","numeric-id":633766,"id":"Q633766"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q533870$9AD55256-6C7E-4946-82DD-92845CC119D1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"9040c31be1bed6e7b338595009bb29e0912a3432","datavalue":{"value":{"entity-type":"item","numeric-id":852886,"id":"Q852886"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q533870$BCA806E8-15AC-4835-B1B6-02FDE380A4F0","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"43ea2b51cc80484ad403eb7e3eb8081bd4bba019","datavalue":{"value":{"entity-type":"item","numeric-id":3034841,"id":"Q3034841"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q533870$D70BA1CF-BE36-4346-9799-BDB62D99C4F8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"4ad374279d8484469bb1c596b93d30bc95ff2bf7","datavalue":{"value":{"entity-type":"item","numeric-id":3817626,"id":"Q3817626"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q533870$577087A1-EA17-47A1-80A9-20ACD22619CA","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"c828406f11016b85eec4e27a91604cf739f622e6","datavalue":{"value":"10.1016/J.TCS.2011.01.006","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q533870$28A2A7E6-7A16-40B5-81DD-BE517297F287","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"a3d8b500308ae68b68bab00239f14239b32a251b","datavalue":{"value":{"entity-type":"item","numeric-id":1318746,"id":"Q1318746"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"544c43fc5559ecdeddf42d89924d68e6446352d4","datavalue":{"value":{"amount":"+0.8883362","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q533870$874EDFBA-4087-4BAA-8577-A429AE0EA63F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"a5c2db26b0bf4ceb99dfca7c1fd7d92937b479fd","datavalue":{"value":{"entity-type":"item","numeric-id":4571483,"id":"Q4571483"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"0d9ad6cced4756f151ba6c25b045bbce4388301c","datavalue":{"value":{"amount":"+0.88092446","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q533870$12CC213E-2EC4-4E12-9E05-00B2905C0FA6","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"cc9c7e3c3a5f4adfa03ee9d0f2861084793eba08","datavalue":{"value":{"entity-type":"item","numeric-id":1303102,"id":"Q1303102"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"851fd4c0baf3def7d77b7f366aa2073d378c68e0","datavalue":{"value":{"amount":"+0.869298","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q533870$80EB4472-2965-48D2-AE7D-2FD013C067A1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"1ea122aaf7828e0233e1443899525117e88ac36f","datavalue":{"value":{"entity-type":"item","numeric-id":340576,"id":"Q340576"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"76a33f7d5ab66c17d1158d9308e91a5fa2581e7d","datavalue":{"value":{"amount":"+0.84681666","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q533870$98CB9255-6312-4D87-B85B-9A9D993D4641","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"e7215d8a6b958ac89b84423bcc7b85795245d136","datavalue":{"value":{"entity-type":"item","numeric-id":3817626,"id":"Q3817626"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"666a4b89ca47c8e76f9dbd3f888df8367d864d1c","datavalue":{"value":{"amount":"+0.84567946","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q533870$D91962F2-3C80-4CEC-B17A-5D4429F4B63C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"19473b8d2f16867822bff40aee3afc2d74aea86a","datavalue":{"value":{"entity-type":"item","numeric-id":3219777,"id":"Q3219777"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"f95421f4f521cd9a8dc8586b6be7328330d1088f","datavalue":{"value":{"amount":"+0.84452176","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q533870$CFB71665-BDF4-400F-8D42-36BA88BF2519","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"ec9f7b9608134891b1ad1f11c1edc45d656a88d0","datavalue":{"value":{"entity-type":"item","numeric-id":5452056,"id":"Q5452056"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"f558618817e7b64efdf7b5ef23dbf10b9012fc88","datavalue":{"value":{"amount":"+0.84200495","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q533870$8099D3B4-71C2-4148-B194-3B26776F2FC6","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"95dbea692226fd15dbd2f3d880b716894b4041ae","datavalue":{"value":{"entity-type":"item","numeric-id":1024784,"id":"Q1024784"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"1a2624b055e16b0bb536f8aac386de272ce7e7d6","datavalue":{"value":{"amount":"+0.84083104","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q533870$EB459F00-0E78-4393-AA65-BF1C78800FF9","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Bitonic sorters of minimal depth","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Bitonic_sorters_of_minimal_depth"}}}}}