Content deleted Content added
Created a stub for Strand sort. Currently doing more research to add to it. |
Added a section for the performance of the algorithm |
||
Line 1:
Strand sort is a very simple [[Recursion (computer science)|recursive]] [[sorting algorithm]] that sorts items of a list into increasing order. It works by moving the first element of a list into a sub-list. Then comparing each subsequent element in the sub-list to the original list and moving each element in the original list that is greater than the element in the sub-list to the sub-list. Then the sub-list is merged into a new list. Repeat this process and merge all sub-lists until all elements are sorted.<ref name=":0">{{Cite book|url=https://www.worldcat.org/oclc/641462443|title=IT enabled practices and emerging management paradigms|date=2008|publisher=Prestige Institute of Management and Research|others=Gupta, I. C. (Ishwar Chandra), 1946-, Jaroliya, Deepak., Prestige Institute of Management and Research.|isbn=9788174466761|edition=1st ed|___location=Indore|oclc=641462443}}</ref> This algorithm is called strand sort because there are strands of sorted elements within the unsorted elements that are removed one at a time.<ref name=":1">{{Cite web|url=https://xlinux.nist.gov/dads/HTML/strandSort.html|title=strand sort|website=xlinux.nist.gov|language=en-US|access-date=2018-11-06}}</ref> This algorithm is also comparison [[sorting algorithm]] because elements of the sub-list are compared to elements of the original list. This algorithm is also used in [[J Sort]] for fewer than 40 elements.<ref>{{Cite book|url=https://www.worldcat.org/oclc/311311576|title=Data structures using C : 1000 problems and solutions|last=Sudipta.|first=Mukherjee,|date=2008|publisher=Tata McGraw-Hill|isbn=9780070667655|___location=New Delhi|oclc=311311576}}</ref>
== Performance == Strand sort has a worst case [[time complexity]] of O(n<sup>2</sup>) which occurs when the input list is reverse sorted.<ref name=":0" /> Where n represents the total number of elements being sorted. Strand sort has a best case [[time complexity]] of O(n) which occurs when the input is a list that is already sorted.<ref name=":1" /> Its average case complexity is O(n log n).<ref name=":0" /> Compared to other [[Sorting algorithm|sorting algorithms]], strand sort is on the slower side.<ref name=":0" />Strand sort is [[Stable algorithm|stable]] due to the fact that the relative order of the elements of the same value does not change. Strand sort is not [[In-place algorithm|in-place]] because it’s space complexity is O(n).<ref name=":0" /> {{AFC submission|t||ts=20181106150605|u=Heldw|ns=118|demo=}}<!-- Important, do not remove this line before article has been created. -->
| |||