{"schema_version":"4ort.packet/1","entity":{"entity_id":"shellsort","kg_uuid":"47270125-6e8b-4c1b-b849-0f3abe413b5f","wikidata_id":"Q848955","name":"shellsort","description":"in-place comparison sorting algorithm invented by D. Shell","type":"Intangible","url":"https://4ort.xyz/entity/shellsort"},"status":"complete","as_of":{"copy_written_at":"2026-11-21T14:52:11Z","last_source_edit_seen":"2026-07-10T13:58:32Z","stale_possible":true,"claims_refreshed_at":null,"source_revision":null},"facts":[{"field":"P31","label":"instance of","value":"sorting algorithm","value_id":"Q181593","value_raw":"Q181593","rank":"normal","current":null,"qualifiers":[],"layer":"source","citation":{"source":"wikidata","source_name":"Wikidata","source_record":"https://www.wikidata.org/wiki/Q848955#P31","source_edition":null,"edition_basis":"unknown","licence":"CC0 1.0 Universal","licence_url":"https://creativecommons.org/publicdomain/zero/1.0/","attribution":null,"references":[{"imported_from":"English Wikipedia"}]},"trust":{"band":"medium","basis":"wikidata-reference-support/2","calibrated":false}},{"field":"P31","label":"instance of","value":"in-place algorithm","value_id":"Q657037","value_raw":"Q657037","rank":"normal","current":null,"qualifiers":[],"layer":"source","citation":{"source":"wikidata","source_name":"Wikidata","source_record":"https://www.wikidata.org/wiki/Q848955#P31","source_edition":null,"edition_basis":"unknown","licence":"CC0 1.0 Universal","licence_url":"https://creativecommons.org/publicdomain/zero/1.0/","attribution":null,"references":[]},"trust":{"band":"unscored","basis":"wikidata-reference-support/2","calibrated":false}},{"field":"P31","label":"instance of","value":"comparison sort","value_id":"Q2632949","value_raw":"Q2632949","rank":"normal","current":null,"qualifiers":[],"layer":"source","citation":{"source":"wikidata","source_name":"Wikidata","source_record":"https://www.wikidata.org/wiki/Q848955#P31","source_edition":null,"edition_basis":"unknown","licence":"CC0 1.0 Universal","licence_url":"https://creativecommons.org/publicdomain/zero/1.0/","attribution":null,"references":[]},"trust":{"band":"unscored","basis":"wikidata-reference-support/2","calibrated":false}},{"field":"P279","label":"subclass of","value":"sorting algorithm","value_id":"Q181593","value_raw":"Q181593","rank":"normal","current":null,"qualifiers":[],"layer":"source","citation":{"source":"wikidata","source_name":"Wikidata","source_record":"https://www.wikidata.org/wiki/Q848955#P279","source_edition":null,"edition_basis":"unknown","licence":"CC0 1.0 Universal","licence_url":"https://creativecommons.org/publicdomain/zero/1.0/","attribution":null,"references":[]},"trust":{"band":"unscored","basis":"wikidata-reference-support/2","calibrated":false}},{"field":"P61","label":"discoverer or inventor","value":"Donald L. Shell","value_id":"Q93133","value_raw":"Q93133","rank":"normal","current":null,"qualifiers":[],"layer":"source","citation":{"source":"wikidata","source_name":"Wikidata","source_record":"https://www.wikidata.org/wiki/Q848955#P61","source_edition":null,"edition_basis":"unknown","licence":"CC0 1.0 Universal","licence_url":"https://creativecommons.org/publicdomain/zero/1.0/","attribution":null,"references":[{"stated_in":"A high-speed sorting procedure","stated_in_id":"Q55880809"}]},"trust":{"band":"high","basis":"wikidata-reference-support/2","calibrated":false}},{"field":"P575","label":"time of discovery or invention","value":"1959","value_id":null,"value_raw":"+1959-00-00T00:00:00Z","rank":"normal","current":null,"qualifiers":[],"layer":"source","citation":{"source":"wikidata","source_name":"Wikidata","source_record":"https://www.wikidata.org/wiki/Q848955#P575","source_edition":null,"edition_basis":"unknown","licence":"CC0 1.0 Universal","licence_url":"https://creativecommons.org/publicdomain/zero/1.0/","attribution":null,"references":[]},"trust":{"band":"unscored","basis":"wikidata-reference-support/2","calibrated":false}},{"field":"P1482","label":"Stack Exchange tag","value":"https://stackoverflow.com/tags/shellsort","value_id":null,"value_raw":"https://stackoverflow.com/tags/shellsort","rank":"normal","current":null,"qualifiers":[],"layer":"source","citation":{"source":"wikidata","source_name":"Wikidata","source_record":"https://www.wikidata.org/wiki/Q848955#P1482","source_edition":null,"edition_basis":"unknown","licence":"CC0 1.0 Universal","licence_url":"https://creativecommons.org/publicdomain/zero/1.0/","attribution":null,"references":[]},"trust":{"band":"unscored","basis":"wikidata-reference-support/2","calibrated":false}},{"field":"P2283","label":"uses","value":"array data structure","value_id":"Q186152","value_raw":"Q186152","rank":"normal","current":null,"qualifiers":[],"layer":"source","citation":{"source":"wikidata","source_name":"Wikidata","source_record":"https://www.wikidata.org/wiki/Q848955#P2283","source_edition":null,"edition_basis":"unknown","licence":"CC0 1.0 Universal","licence_url":"https://creativecommons.org/publicdomain/zero/1.0/","attribution":null,"references":[{"imported_from":"English Wikipedia"}]},"trust":{"band":"medium","basis":"wikidata-reference-support/2","calibrated":false}},{"field":"P2534","label":"defining formula","value":"W_{v}(s + 1) = W_{v}(s) + \\theta(u, v, s) \\cdot \\alpha(s) \\cdot (D(t) - W_{v}(s))","value_id":null,"value_raw":"W_{v}(s + 1) = W_{v}(s) + \\theta(u, v, s) \\cdot \\alpha(s) \\cdot (D(t) - W_{v}(s))","rank":"normal","current":null,"qualifiers":[],"layer":"source","citation":{"source":"wikidata","source_name":"Wikidata","source_record":"https://www.wikidata.org/wiki/Q848955#P2534","source_edition":null,"edition_basis":"unknown","licence":"CC0 1.0 Universal","licence_url":"https://creativecommons.org/publicdomain/zero/1.0/","attribution":null,"references":[{"imported_from":"English Wikipedia"}]},"trust":{"band":"medium","basis":"wikidata-reference-support/2","calibrated":false}},{"field":"P2812","label":"MathWorld ID","value":"Shellsort","value_id":null,"value_raw":"Shellsort","rank":"normal","current":null,"qualifiers":[{"field":"P1810","label":"subject named as","value":"Shellsort"}],"layer":"source","citation":{"source":"wikidata","source_name":"Wikidata","source_record":"https://www.wikidata.org/wiki/Q848955#P2812","source_edition":null,"edition_basis":"unknown","licence":"CC0 1.0 Universal","licence_url":"https://creativecommons.org/publicdomain/zero/1.0/","attribution":null,"references":[]},"trust":{"band":"unscored","basis":"wikidata-reference-support/2","calibrated":false}},{"field":"P3752","label":"worst-case time complexity","value":"O(n^2)","value_id":null,"value_raw":"O(n^2)","rank":"normal","current":null,"qualifiers":[],"layer":"source","citation":{"source":"wikidata","source_name":"Wikidata","source_record":"https://www.wikidata.org/wiki/Q848955#P3752","source_edition":null,"edition_basis":"unknown","licence":"CC0 1.0 Universal","licence_url":"https://creativecommons.org/publicdomain/zero/1.0/","attribution":null,"references":[{"url":"http://www.dtic.mil/get-tr-doc/pdf?AD=AD0740110","title":"Shellsort and Sorting Networks (Outstanding Dissertations in the Computer Sciences)"}]},"trust":{"band":"high","basis":"wikidata-reference-support/2","calibrated":false}},{"field":"P3753","label":"best-case time complexity","value":"O (n \\log n)","value_id":null,"value_raw":"O (n \\log n)","rank":"normal","current":null,"qualifiers":[],"layer":"source","citation":{"source":"wikidata","source_name":"Wikidata","source_record":"https://www.wikidata.org/wiki/Q848955#P3753","source_edition":null,"edition_basis":"unknown","licence":"CC0 1.0 Universal","licence_url":"https://creativecommons.org/publicdomain/zero/1.0/","attribution":null,"references":[{"url":"https://www.cs.wcupa.edu/rkline/ds/shell-comparison.html"},{"imported_from":"English Wikipedia"}]},"trust":{"band":"high","basis":"wikidata-reference-support/2","calibrated":false}},{"field":"P3754","label":"average time complexity","value":"O(n^{1.25})","value_id":null,"value_raw":"O(n^{1.25})","rank":"normal","current":null,"qualifiers":[{"field":"P5102","label":"nature of statement","value":"conjecture"}],"layer":"source","citation":{"source":"wikidata","source_name":"Wikidata","source_record":"https://www.wikidata.org/wiki/Q848955#P3754","source_edition":null,"edition_basis":"unknown","licence":"CC0 1.0 Universal","licence_url":"https://creativecommons.org/publicdomain/zero/1.0/","attribution":null,"references":[{"url":"https://www.cs.wcupa.edu/rkline/ds/shell-comparison.html"}]},"trust":{"band":"high","basis":"wikidata-reference-support/2","calibrated":false}},{"field":"P3755","label":"worst-case space complexity","value":"O(1)","value_id":null,"value_raw":"O(1)","rank":"normal","current":null,"qualifiers":[],"layer":"source","citation":{"source":"wikidata","source_name":"Wikidata","source_record":"https://www.wikidata.org/wiki/Q848955#P3755","source_edition":null,"edition_basis":"unknown","licence":"CC0 1.0 Universal","licence_url":"https://creativecommons.org/publicdomain/zero/1.0/","attribution":null,"references":[{"url":"https://www.cs.wcupa.edu/rkline/ds/shell-comparison.html"}]},"trust":{"band":"high","basis":"wikidata-reference-support/2","calibrated":false}},{"field":"P5047","label":"Rosetta Code page ID","value":"Sorting_algorithms/Shell_sort","value_id":null,"value_raw":"Sorting_algorithms/Shell_sort","rank":"normal","current":null,"qualifiers":[],"layer":"source","citation":{"source":"wikidata","source_name":"Wikidata","source_record":"https://www.wikidata.org/wiki/Q848955#P5047","source_edition":null,"edition_basis":"unknown","licence":"CC0 1.0 Universal","licence_url":"https://creativecommons.org/publicdomain/zero/1.0/","attribution":null,"references":[]},"trust":{"band":"unscored","basis":"wikidata-reference-support/2","calibrated":false}},{"field":"P5106","label":"Dictionary of Algorithms and Data Structures ID","value":"shellsortI","value_id":null,"value_raw":"shellsortI","rank":"normal","current":null,"qualifiers":[],"layer":"source","citation":{"source":"wikidata","source_name":"Wikidata","source_record":"https://www.wikidata.org/wiki/Q848955#P5106","source_edition":null,"edition_basis":"unknown","licence":"CC0 1.0 Universal","licence_url":"https://creativecommons.org/publicdomain/zero/1.0/","attribution":null,"references":[]},"trust":{"band":"unscored","basis":"wikidata-reference-support/2","calibrated":false}},{"field":"P6104","label":"maintained by WikiProject","value":"WikiProject Mathematics","value_id":"Q8487137","value_raw":"Q8487137","rank":"normal","current":null,"qualifiers":[],"layer":"source","citation":{"source":"wikidata","source_name":"Wikidata","source_record":"https://www.wikidata.org/wiki/Q848955#P6104","source_edition":null,"edition_basis":"unknown","licence":"CC0 1.0 Universal","licence_url":"https://creativecommons.org/publicdomain/zero/1.0/","attribution":null,"references":[]},"trust":{"band":"unscored","basis":"wikidata-reference-support/2","calibrated":false}},{"field":"P6366","label":"Microsoft Academic ID (discontinued)","value":"105089967","value_id":null,"value_raw":"105089967","rank":"normal","current":null,"qualifiers":[],"layer":"source","citation":{"source":"wikidata","source_name":"Wikidata","source_record":"https://www.wikidata.org/wiki/Q848955#P6366","source_edition":null,"edition_basis":"unknown","licence":"CC0 1.0 Universal","licence_url":"https://creativecommons.org/publicdomain/zero/1.0/","attribution":null,"references":[]},"trust":{"band":"unscored","basis":"wikidata-reference-support/2","calibrated":false}},{"field":"P10565","label":"Encyclopedia of China (Third Edition) old ID (2021)","value":"375969","value_id":null,"value_raw":"375969","rank":"normal","current":null,"qualifiers":[],"layer":"source","citation":{"source":"wikidata","source_name":"Wikidata","source_record":"https://www.wikidata.org/wiki/Q848955#P10565","source_edition":null,"edition_basis":"unknown","licence":"CC0 1.0 Universal","licence_url":"https://creativecommons.org/publicdomain/zero/1.0/","attribution":null,"references":[]},"trust":{"band":"unscored","basis":"wikidata-reference-support/2","calibrated":false}}],"unknowns":[],"omitted":{"facts":0,"reason":null},"licences":[{"source":"wikidata","source_name":"Wikidata","licence":"CC0 1.0 Universal","licence_url":"https://creativecommons.org/publicdomain/zero/1.0/","attribution":null,"fields":["P31","P279","P61","P575","P1482","P2283","P2534","P2812","P3752","P3753","P3754","P3755","P5047","P5106","P6104","P6366","P10565"]}],"routes":{"entity_page":"https://4ort.xyz/entity/shellsort","packet_api":"https://4ort.xyz/api/v1/entities/shellsort/packet","facts_jsonld":"https://4ort.xyz/entity/shellsort/facts.json","changes_api":"https://4ort.xyz/api/v1/knowledge/get_entity_changes?entity=shellsort","attention_api":"https://4ort.xyz/api/v1/knowledge/get_attention?entity=shellsort","wikidata":"https://www.wikidata.org/wiki/Q848955","official_website":null},"trust_rules":{"wikidata-reference-support/2":"From the references in our copy of the statement: high = it cites a source (stated in P248, or a reference URL that is not Wikipedia); medium = only 'imported from Wikimedia project' or a Wikipedia URL; unscored = our copy holds no reference (older copies dropped references, so this is not evidence that Wikidata has none). Wikidata may hold more references than our copy shows. Reference support, not a probability."},"notes":["Our copy of this item's statements has not been checked against Wikidata since tracking began (2026-10-25); a newer value may exist."]}