{"entities":{"Q7361878":{"pageid":31521173,"ns":120,"title":"Item:Q7361878","lastrevid":105370031,"modified":"2026-10-07T13:38:45Z","type":"item","id":"Q7361878","labels":{"en":{"language":"en","value":"Lower bound on comparison-based sorting algorithms"}},"descriptions":{"en":{"language":"en","value":"AFP entry Comparison_Sort_Lower_Bound"}},"aliases":{},"claims":{"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"100c923261a5794e7dc0a2456b709b9e5176e797","datavalue":{"value":"https://isa-afp.org/entries/Comparison_Sort_Lower_Bound.html","type":"string"},"datatype":"url"},"type":"statement","id":"Q7361878$9888327A-959C-43BF-B1BF-7D4FF349D463","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"df40c95188c41d28e5f7c0a0b44ffb08645bbac7","datavalue":{"value":{"time":"+2017-03-15T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q7361878$9A587E6D-1E5D-48CF-A472-504D76BF7C34","rank":"normal"}],"P43":[{"mainsnak":{"snaktype":"value","property":"P43","hash":"85859c7ab42dcb8b36208f2902b7ce0d86423a6f","datavalue":{"value":"Manuel Eberl","type":"string"},"datatype":"string"},"type":"statement","id":"Q7361878$1948853A-8372-4537-AAC6-0C91BA1B2CAA","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"a6d11f4b043ae8c7825a6ab21a3975e5b8e1bce0","datavalue":{"value":{"text":"Lower bound on comparison-based sorting algorithms","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q7361878$E092B401-F30D-4217-875D-4FA54F277275","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"a01edf17685e74d162fbb01cb1d94978045e5f7c","datavalue":{"value":"This article contains a formal proof of the well-known fact that number of comparisons that a comparison-based sorting algorithm needs to perform to sort a list of length n is at least log 2 (n!) in the worst case, i. e. \u03a9(n log n) . For this purpose, a shallow embedding for comparison-based sorting algorithms is defined: a sorting algorithm is a recursive datatype containing either a HOL function or a query of a comparison oracle with a continuation containing the remaining computation. This makes it possible to force the algorithm to use only comparisons and to track the number of comparisons made.","type":"string"},"datatype":"string"},"type":"statement","id":"Q7361878$C8B5962F-BF04-47B3-8B4F-D34A63E268EC","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"3bffe48c7c76b90bf68970921698e19786e1600b","datavalue":{"value":{"entity-type":"item","numeric-id":2747613,"id":"Q2747613"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q7361878$5D82E481-6B6D-4F25-ADFE-31783DDD0DAB","rank":"normal"}],"P37":[{"mainsnak":{"snaktype":"value","property":"P37","hash":"9a21a8eebe97539644aa32b24dda137c12e751dc","datavalue":{"value":{"entity-type":"item","numeric-id":40327,"id":"Q40327"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q7361878$11E80899-8AFC-492F-8B9E-74D95136BEB5","rank":"normal"}],"P585":[{"mainsnak":{"snaktype":"value","property":"P585","hash":"4e61d5c4974522a5fe3780c9295027ba96d92743","datavalue":{"value":{"entity-type":"item","numeric-id":7361487,"id":"Q7361487"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q7361878$ACD9324A-A13C-42EE-9D3B-A4CB76157F27","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P585","hash":"e0b5465b6a0d9e05645cdb7168eee1aaf7eb2845","datavalue":{"value":{"entity-type":"item","numeric-id":7361518,"id":"Q7361518"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q7361878$896F62D3-06A2-4BF4-BC3C-E3FD99396E1F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P585","hash":"b3b498344487dda98f673ddf873bb5beca1d9e91","datavalue":{"value":{"entity-type":"item","numeric-id":7361438,"id":"Q7361438"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q7361878$2342FADB-4D7B-4BED-8FB2-5DEB67BB1E1F","rank":"normal"}],"P2651":[{"mainsnak":{"snaktype":"value","property":"P2651","hash":"1157f6239d5752bb0ad1cee836272bd46c6bf40f","datavalue":{"value":{"entity-type":"item","numeric-id":7360772,"id":"Q7360772"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q7361878$ACE5B888-1677-4D82-A901-B78DDA89B7EF","rank":"normal"}],"P1460":[{"mainsnak":{"snaktype":"value","property":"P1460","hash":"908c3454b3659c4b140ccce33c5aee31081edc8d","datavalue":{"value":{"entity-type":"item","numeric-id":5976450,"id":"Q5976450"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q7361878$8DD8BBBC-E357-4742-8C44-D732125ED118","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Lower bound on comparison-based sorting algorithms","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Lower_bound_on_comparison-based_sorting_algorithms"}}}}}