Strand Sort Implementation in Python

Strand Sort is a sorting algorithm that works by repeatedly pulling out sorted sublists from the unsorted list and merging them together until the whole list is sorted. It is a recursive algorithm that can be implemented using a linked list or an array. In this article, we will discuss how Strand Sort works, its implementation in Python, and its time and space complexity.

How Algorithm Works

The algorithm starts by selecting the first element of the input list and creating a new list with only that element. It then iterates over the remaining elements of the input list, adding each element to the new list if it is greater than or equal to the last element of the new list. If the element is less than the last element of the new list, it is added to another list called the “strand”. This process is repeated until all the elements of the input list have been processed.

Once the first strand has been created, it is merged with the initial sorted list. To do this, the algorithm compares the first element of the strand with the first element of the sorted list. If the element of the strand is less than the element of the sorted list, it is removed from the strand and added to the sorted list. If the element of the strand is greater than or equal to the element of the sorted list, the algorithm moves to the next element of the sorted list.

The algorithm repeats the above steps until there are no more elements in the strand. It then repeats the entire process, creating new strands and merging them with the sorted list, until the entire input list has been sorted.

Algorithm Implementation

Here is the implementation of Strand Sort in Python:

def strand_sort(arr):
    if len(arr) == 1:
        return arr
    else:
        sublist = [arr[0]]
        del arr[0]
        for i in arr:
            if i >= sublist[-1]:
                sublist.append(i)
            else:
                break
        strand = [i for i in arr if i < sublist[-1]] remaining = [i for i in arr if i >= sublist[-1]]
        new_list = sublist + strand
        return merge_lists(new_list, strand_sort(remaining))

def merge_lists(list1, list2):
    i = 0
    j = 0
    result = []
    while i < len(list1) and j < len(list2):
        if list1[i] < list2[j]:
            result.append(list1[i])
            i += 1
        else:
            result.append(list2[j])
            j += 1
    result += list1[i:]
    result += list2[j:]
    return result

The above implementation takes an array as input and sorts it using Strand Sort. The algorithm is implemented recursively using two functions: strand_sort() and merge_lists().

The strand_sort() function takes an array as input and returns the sorted array. If the length of the array is 1, it simply returns the array. Otherwise, it creates a sublist with the first element of the array and iterates over the remaining elements, adding each element to the sublist if it is greater than or equal to the last element of the sublist. If the element is less than the last element of the sublist, it is added to a new list called the “strand”. The remaining elements of the input array are also split into two lists: one containing elements greater than or equal to the last element of the sublist, and the other containing elements less than the last element of the sublist. The function then recursively calls itself with the remaining list, and merges the sorted sublist and strand with the sorted remaining list using the merge_lists() function.

The merge_lists() function takes two lists as input and merges them into a single sorted list. It iterates over the two lists, comparing the first elements of each list and adding the smaller one to the result list. It then moves to the next element of the list with the smaller element, until all the elements of both lists have been added to the result list.

Time and Space Complexity

The time complexity of Strand Sort depends on the length of the input array and the number of strands that are created during the sorting process. The worst-case time complexity is O(n^2), which occurs when the input array is in reverse order. The best-case time complexity is O(n log n), which occurs when the input array is already sorted.

The space complexity of Strand Sort is O(n), where n is the length of the input array. This is because the algorithm creates new lists and strands during the sorting process, which can take up additional memory space.

Example Run

Let’s run an example of Strand Sort on an unsorted list of integers:

unsorted_list = [9, 5, 2, 8, 7, 1, 3, 6, 4]
sorted_list = strand_sort(unsorted_list)
print(sorted_list)

The output of the above code should be:

[1, 2, 3, 4, 5, 6, 7, 8, 9]

In the above example, we passed an unsorted list of integers to the strand_sort() function, which returned a sorted list.

Conclusion

Strand Sort is a sorting algorithm that works by repeatedly pulling out sorted sublists from the unsorted list and merging them together until the whole list is sorted. It is a recursive algorithm that can be implemented using a linked list or an array. Although its worst-case time complexity is O(n^2), it has a best-case time complexity of O(n log n) when the input array is already sorted. Its space complexity is O(n), where n is the length of the input array.

In this article, we discussed how Strand Sort works and its implementation in Python. We also looked at its time and space complexity, and ran an example of Strand Sort on an unsorted list of integers.