{"entities":{"Q1069307":{"pageid":1080059,"ns":120,"title":"Item:Q1069307","lastrevid":69562779,"modified":"2026-04-13T07:51:47Z","type":"item","id":"Q1069307","labels":{"en":{"language":"en","value":"Improved upper bounds on Shellsort"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 3934420"}},"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":"Q1069307$FA12AA47-22D6-43B0-ADA6-CB695327206B","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"f2ac227936c4b1255cd5d1161a483cbc27e532b6","datavalue":{"value":{"text":"Improved upper bounds on Shellsort","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1069307$0729A6E3-BD04-4FCF-B9DA-A65796521828","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"686dd33b38fdb3197a1868e663f809791dddf297","datavalue":{"value":"0583.68035","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1069307$0F4DEB3D-B3FF-44BC-9F77-C48380F1322D","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"0fefd0c4982748a1b94601baa7ade775e8f46e66","datavalue":{"value":"10.1016/0022-0000(85)90042-X","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1069307$B7D1803B-7F5F-4255-9D4F-BCE3C1A07F3C","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"38f72880a8f9a78c5019282fe96e1dbb19b86959","datavalue":{"value":{"entity-type":"item","numeric-id":1069306,"id":"Q1069306"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1069307$69D20198-7425-4E0B-B730-695B7B0EE77A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"05f69778b33fb8610e018d9c2ee4606d4897f942","datavalue":{"value":{"entity-type":"item","numeric-id":672984,"id":"Q672984"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1069307$EE1436EE-3721-4888-BB66-3DFE1C6C0EFC","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"3340243f57e05f2265c56423c388055a14b114fa","datavalue":{"value":{"entity-type":"item","numeric-id":107189,"id":"Q107189"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1069307$1535DD50-8C06-4365-9DFD-34A1A6AF0CD5","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"3c94df5c9af0ede578c52141befd29044de13172","datavalue":{"value":{"time":"+1985-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":"Q1069307$77C9A7C5-F273-4692-9C07-DF70CC7AC3D6","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"17064f655b06356e69607b5bb5eed51c031db0d6","datavalue":{"value":"The running time of Shellsort, with the number of passes restricted to O(log N), was thought for some time to be \\(\\Theta (N^{3/2})\\), due to general results of Pratt. Sedgewick recently gave an \\(O(N^{4/3})\\) bound, but extensions of his method to provide better bounds seem to require new results on a classical problem in number theory. In this paper, we use a different approach to achieve \\(O(N^{1+\\epsilon /\\sqrt{lg N}})\\), for any \\(\\epsilon >0\\).","type":"string"},"datatype":"string"},"type":"statement","id":"Q1069307$D73037A2-4CCE-4FDA-8CD5-28F3F72DD6CE","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"3f97694d44af155a68434cb72eabc6a4d5dd5227","datavalue":{"value":"68P10","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1069307$B60ECBF0-E9F5-4DF6-BCD2-7A645BAB8A00","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"fdd9498216d1fd2eff80e5a7d18782b649eb7b2f","datavalue":{"value":"68Q25","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1069307$192B5B3A-6F8A-4318-A0D2-17BB6DD47170","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"34c57f7a10655eef2f5ec8f33f977cbf6954dd87","datavalue":{"value":"3934420","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1069307$38608CB3-0475-4DDB-AA06-8E2BB173A414","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"1f11a697ca4320b2c5e334107aae45a37f7f8f8b","datavalue":{"value":"sorting","type":"string"},"datatype":"string"},"type":"statement","id":"Q1069307$8454ABCE-8F02-45B0-96BE-5EE54D16613A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"2f3d4c4f0402aa58af4ddf1e2cea9445dfba8f84","datavalue":{"value":"running time","type":"string"},"datatype":"string"},"type":"statement","id":"Q1069307$336FEB6C-1343-40D3-A784-D9CF3A7443CE","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":"Q1069307$3D405DCF-D0AC-4883-9D45-2C0BE4B5F2D1","rank":"normal"}],"P12":[{"mainsnak":{"snaktype":"value","property":"P12","hash":"dce942c5b431d761a4667581dc14a511a4b2ee9f","datavalue":{"value":"Q56113002","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1069307$F71DE0AF-8EE4-4DA8-9B03-B91A26AC17B8","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"a832610fe6a02adc6f805fa57fb8dcb16628143d","datavalue":{"value":{"entity-type":"item","numeric-id":3827548,"id":"Q3827548"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1069307$F28FEEE6-3B42-472F-8C08-6E90BF48ACD0","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"5c424df6fe3bb17568b9cbca6be95cb19e5380ca","datavalue":{"value":{"entity-type":"item","numeric-id":3274228,"id":"Q3274228"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1069307$3E8ECE3A-2F98-4519-8F30-6192CCB52215","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":"Q1069307$B1C7F5A3-7047-4A6D-992C-CDF9EF78A792","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"560cf79f2da7cba5ae2e5720b94d4db8d7e82ec9","datavalue":{"value":{"entity-type":"item","numeric-id":3219774,"id":"Q3219774"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1069307$6873E85A-35E9-43AB-93B4-24D24C7C26C0","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"b5827b33f6040e2365ba104b2c460c40532349bb","datavalue":{"value":{"entity-type":"item","numeric-id":3311639,"id":"Q3311639"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1069307$0670FB47-0285-4C0E-A1AA-BBA24EFED793","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"adda3d37a312940cfedd266a5246399b5ed3c707","datavalue":{"value":{"entity-type":"item","numeric-id":3742727,"id":"Q3742727"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1069307$74D3CA77-8166-4763-9D8B-9F476AB30EF8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"1f1082d594e0074f838e393fb93a89f6029dfc13","datavalue":{"value":{"entity-type":"item","numeric-id":4119256,"id":"Q4119256"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1069307$3706CE3F-C1BE-4456-8968-A797632A8A27","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"be57927d3e207dacdf9159ad6c9a7ae20a730d23","datavalue":{"value":"https://doi.org/10.1016/0022-0000(85)90042-x","type":"string"},"datatype":"url"},"type":"statement","id":"Q1069307$B78B5E95-4AF7-418E-8B25-73FB0B9C8702","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"843dfe3041360542b8960afb49ac2680411c67b3","datavalue":{"value":"W2035580504","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1069307$61765482-1428-47FC-9EED-D567C5224CA4","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"cc5a74f2dd58f353cb4587e1cc9f0fe596bf95ee","datavalue":{"value":{"entity-type":"item","numeric-id":3742727,"id":"Q3742727"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"8164ae23b19d89060fbdfd134481400f91e8ed91","datavalue":{"value":{"amount":"+0.892220675945282","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":"Q1069307$7D2BE2D0-64DE-453F-B048-1E35882C0BA0","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"171fd6fae0fc80195b3d97d48a655b0a2df00fa5","datavalue":{"value":{"entity-type":"item","numeric-id":3493227,"id":"Q3493227"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"ba358af48e516e61ffe43fe8e705d95aed56f5bc","datavalue":{"value":{"amount":"+0.8637087941169739","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":"Q1069307$40FA0021-5EFA-423E-9C9F-44F256AE8B14","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"15d7996b8af199c4e536d1e1bbcf28d425865e3a","datavalue":{"value":{"entity-type":"item","numeric-id":1816996,"id":"Q1816996"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"13af0d71324136c5c537fe5592ce24993cdb38c7","datavalue":{"value":{"amount":"+0.8602690100669861","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":"Q1069307$3E9613C7-E7E9-469D-9F5B-B4C1A0B9F865","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"ac59259de3d67a30dd32b71f1384dd8abb06b7ba","datavalue":{"value":{"entity-type":"item","numeric-id":4230344,"id":"Q4230344"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"017e7c4e69e5ffc9d5583f6e1e0571e11a52533c","datavalue":{"value":{"amount":"+0.8393774628639221","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":"Q1069307$FBA65B8D-5CB6-4F10-A336-E5D367AED6EF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"29e2441b115685418af14dd4dca3e8584b31be1e","datavalue":{"value":{"entity-type":"item","numeric-id":4339002,"id":"Q4339002"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"59b671c15de53d75b305216d7ed202f6ff4413cd","datavalue":{"value":{"amount":"+0.8328268527984619","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":"Q1069307$9656D7AA-0EB1-431D-B0B1-4750C3661754","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Improved upper bounds on Shellsort","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Improved_upper_bounds_on_Shellsort"}}}}}