Insertion Sort, Merge Sort

Insertion Sort

Insertion sort – each element is compared to the previous item in the list and inserted in place of more. Since the items are sorted from first to last, then each successive element is compared with pre-sorted list that *might* reduce the total time. Time complexity O(n^2), that is identical to the bubble sort.

Merge Sort

Merge sort – the list is divided into groups of one element, then the group “merge” in pairs with simultaneous comparison. In my implementation at the merge of pairs elements to the left compared with the right elements, and then moved to the result list, if the items in left are over, then right list elements added to resulting list (their extra comparison is unnecessary, since all the elements in the groups are sorted by iterations)
The operation of this algorithm is very easy to parallelize, pairs merging step can be performed in threads, with thread dispatcher wait.
Algorithm output for single-threaded performance:


["John", "Alice", "Mike", "#1", "Артем", "20", "60", "60", "DoubleTrouble"]
[["John"], ["Alice"], ["Mike"], ["#1"], ["Артем"], ["20"], ["60"], ["60"], ["DoubleTrouble"]]
[["Alice", "John"], ["#1", "Mike"], ["20", "Артем"], ["60", "60"], ["DoubleTrouble"]]
[["#1", "Alice", "John", "Mike"], ["20", "60", "60", "Артем"], ["DoubleTrouble"]]
[["#1", "20", "60", "60", "Alice", "John", "Mike", "Артем"], ["DoubleTrouble"]]
["#1", "20", "60", "60", "Alice", "DoubleTrouble", "John", "Mike", "Артем"]

Algorithm output for multithreaded execution:


["John", "Alice", "Mike", "#1", "Артем", "20", "60", "60", "DoubleTrouble"]
[["John"], ["Alice"], ["Mike"], ["#1"], ["Артем"], ["20"], ["60"], ["60"], ["DoubleTrouble"]]
[["20", "Артем"], ["Alice", "John"], ["60", "60"], ["#1", "Mike"], ["DoubleTrouble"]]
[["#1", "60", "60", "Mike"], ["20", "Alice", "John", "Артем"], ["DoubleTrouble"]]
[["DoubleTrouble"], ["#1", "20", "60", "60", "Alice", "John", "Mike", "Артем"]]
["#1", "20", "60", "60", "Alice", "DoubleTrouble", "John", "Mike", "Артем"]

Time complexity O (n * log (n)), which is slightly better than O (n ^ 2)

References

https://en.wikipedia.org/wiki/Insertion_sort
https://en.wikipedia.org/wiki/Merge_sort

Source Code

https://gitlab.com/demensdeum/algorithms

0