2.1 Merge sort Flashcards
merge sort algorithm
breaks a list into its component parts and then builds it up again with them in the correct order
stages of a merge sort
- the list is broken in half until each item is its own list
- adjacent lists are joined together and the items are compared against each other to form ordered lists of two
- the first item in the merged lists is compared against the other first item in the list to determine which one comes first
- this is repeated until the whole list is merged
-the lists continue to be joined and sorted until there is one final, ordered list
recursion
repeating a process using the results of the first application
the lists are divided into two repeatedly, and the results are then recursively reassembled in ascending order
is often used in algorithms and can be implemented by creating a function that calls itself instead of returning to the main program
Describe how data is sorted into ascending order using the merge sort algorithm [2]
the list is divided into two repeatedly until each list has only one item
the lists are then progressively merged with the adjacent list with the items in ascending order
the first item in the merged lists is compared against the other first item in the list to determine which one comes first
this is repeated until the whole list is merged
Show the stages of a merge sort when used to sort the following list of numbers n to ascending order.
38 27 43 3 9 82 10 [5]
38 27 43 3 9 82 10
38 27 43 3 9 82 10
38 27 43 3 9 82 10
38 27 43 3 9 82 10
27 38 3 43 9 82 10
3 27 38 43 9 10 82
3 9 10 27 38 43 82
