How does a computer sort numbers?

One pass of bubble sort is not enough because smaller numbers may still be out of order. The computer repeats passes over the list. Each pass pushes the next largest number to its correct place at the end. For example, after the first pass, the list is 72, 85, 65, 90. A second pass gives 72, 65, 85, 90. A third pass gives 65, 72, 85, 90. When a pass makes no swaps, the list is sorted. 7

Divide and combine is another approach: split the list into smaller parts, sort each part, then merge them. For example, split 85, 72, 90, 65 into two lists: 85, 72 and 90, 65. Sort each: 72, 85 and 65, 90. Then merge the two sorted lists into one sorted list: 65, 72, 85, 90. This method is often faster for large lists. 8

Merging two sorted piles means building one sorted pile by repeatedly picking the smaller top card. For example, pile A: 72, 85 and pile B: 65, 90. Compare top cards: 72 and 65; pick 65. Then compare 72 and 90; pick 72. Then compare 85 and 90; pick 85. Then pick 90. The merged pile is 65, 72, 85, 90. 9

Selection sort finds the smallest number and moves it to the front. Scan the list to find the smallest, then swap it with the first item. For example, with 85, 72, 90, 65, the smallest is 65; swap with 85 to get 65, 72, 90, 85. Then find the smallest in the rest (72, 90, 85): it's 72, already in place. Then find the smallest in 90, 85: it's 85; swap with 90 to get 65, 72, 85, 90. 10

Different sorting methods need different amounts of work. Bubble sort compares neighbors many times, especially on large lists. Merge sort splits and merges, which can be faster for big lists. For example, sorting 10 numbers might take about 100 comparisons with bubble sort but fewer with merge sort. Counting comparisons and swaps helps you compare speed. 11

Some sorting methods sort in place, using no extra memory beyond the list itself. Others need extra space for copies. For example, bubble sort and selection sort work in place: they only swap items within the list. Merge sort needs extra space to hold the divided parts before merging. If memory is limited, an in-place method may be better. 12

The size of the data matters: sorting 100 numbers takes more work than sorting 10. The existing order also matters: an almost sorted list can be much faster for some methods. For example, bubble sort on an already sorted list needs only one pass with no swaps. A shuffled list needs many passes. So the computer's work depends on both size and order. 13

The type of values affects sorting. Numbers are compared by size, but words are compared alphabetically. For example, sorting names like Alice, Bob, Carol uses alphabetical order. Some methods work well for numbers but need adjustments for words. The kind of value guides which sorting method fits best. 14

Beginners often stop after one pass of bubble sort, but one pass is not enough. Another mistake is forgetting that a list might already be sorted; check for that. Also, test with small lists and tricky cases like duplicate numbers or reverse order. For example, test sorting 3, 2, 1 and 1, 1, 1 to catch errors. 15

Computers sort by comparing and moving numbers, using methods that differ in speed and memory. Bubble sort swaps neighbors repeatedly; merge sort divides and combines. The amount of data, the existing order, and the type of values guide the choice. Remember to test with small and tricky examples to ensure correctness. 16