 onlyforbopi
1/4/2017 - 6:54 AM

## Linux.Bash.Sorting

Linux.Bash.Sorting #linux #bash #sorting #bubble #insertionsort #selectionsort #numerical

BASH_SORTING

``````#!/bin/bash

# Necessary
source MOD.MinMax.bsh

# SELECTION SORT
#In computer science, selection sort is a sorting algorithm, specifically an in-place comparison sort.
#It has O(n2) time complexity, making it inefficient on large lists, and generally performs worse than
#the similar insertion sort. Selection sort is noted for its simplicity, and it has performance advantages
#over more complicated algorithms in certain situations, particularly where auxiliary memory is limited.
#The algorithm divides the input list into two parts: the sublist of items already sorted, which is built
#up from left to right at the front (left) of the list, and the sublist of items remaining to be sorted
#that occupy the rest of the list. Initially, the sorted sublist is empty and the unsorted sublist is the
#entire input list. The algorithm proceeds by finding the smallest (or largest, depending on sorting
#order) element in the unsorted sublist, exchanging (swapping) it with the leftmost unsorted element
#(putting it in sorted order), and moving the sublist boundaries one element to the right.

### NUMERICAL SORTING
##
# selsort():   (Selection Sort)
# Worst-case:  Ξ©(N^2) (slow)
# Stability:   stable
# Sensitivity: insensitive
# Use:         Quickly find extrema for unordered data
# Called as: selsort 1 3 4 5 6 3 4 5 6
# Alternate : selsort \${array[*]}
# Output : \${SORTEDARRAY[*]}
# Sorts in ASCENDING ORDER / NUMERICAL
selsort() {
local i m x j t
SORTEDARRAY=("\$@")
for (( i=0; i < \${#SORTEDARRAY[@]}; i++ )); do
(( m=i ))
x="\${SORTEDARRAY[m]}" # The minimum value
for (( j=i+1; j < \${#SORTEDARRAY[@]}; j++ )); do
compare "\${SORTEDARRAY[j]}" \$x
(( \$? == 2 )) || continue
(( m=j ))
x="\${SORTEDARRAY[j]}"
done

# Swap if needed
(( m == i )) && continue
t="\${SORTEDARRAY[m]}" # Placeholder for swapping elements
SORTEDARRAY[m]="\${SORTEDARRAY[i]}"
SORTEDARRAY[i]="\$t"
done
}

# selsortrev():   (Selection Sort)
# Worst-case:  Ξ©(N^2) (slow)
# Stability:   stable
# Sensitivity: insensitive
# Use:         Quickly find extrema for unordered data
# Called as: selsort 1 3 4 5 6 3 4 5 6
# Alternate : selsort \${array[*]}
# Output : \${SORTEDARRAY[*]}
# Sorts in DESCENDING ORDER / NUMERICAL
selsortrev() {
local i m x j t
SORTEDARRAY=("\$@")
for (( i=0; i < \${#SORTEDARRAY[@]}; i++ )); do
(( m=i ))
x="\${SORTEDARRAY[m]}" # The minimum value
for (( j=i+1; j < \${#SORTEDARRAY[@]}; j++ )); do
compare "\${SORTEDARRAY[j]}" \$x
(( \$? == 3 )) || continue
(( m=j ))
x="\${SORTEDARRAY[j]}"
done

# Swap if needed
(( m == i )) && continue
t="\${SORTEDARRAY[m]}" # Placeholder for swapping elements
SORTEDARRAY[m]="\${SORTEDARRAY[i]}"
SORTEDARRAY[i]="\$t"
done
}

### LEXICAL SORTING
##
# selsortlex():   (Selection Sort)
# Worst-case:  Ξ©(N^2) (slow)
# Stability:   stable
# Sensitivity: insensitive
# Use:         Quickly find extrema for unordered data
# Called as: selsort STRING1 STRING 2 STRING 3
# Alternate : selsort \${array[*]}
# Output : \${SORTEDARRAY[*]}
# Sorts in ASCENDING ORDER / LEXICAL
selsortlex(){
local i m x j t
SORTEDARRAY=("\$@")
for (( i=0; i < \${#SORTEDARRAY[@]}; i++ )); do
(( m=i ))
x="\${SORTEDARRAY[m]}" # The minimum value
for (( j=i+1; j < \${#SORTEDARRAY[@]}; j++ )); do
compare LEX "\${SORTEDARRAY[j]}" \$x
(( \$? == 2 )) || continue
(( m=j ))
x="\${SORTEDARRAY[j]}"
done

# Swap if needed
(( m == i )) && continue
t="\${SORTEDARRAY[m]}" # Placeholder for swapping elements
SORTEDARRAY[m]="\${SORTEDARRAY[i]}"
SORTEDARRAY[i]="\$t"
done
}

# selsortlexrev():   (Selection Sort)
# Worst-case:  Ξ©(N^2) (slow)
# Stability:   stable
# Sensitivity: insensitive
# Use:         Quickly find extrema for unordered data
# Called as: selsort STRING1 STRING 2 STRING 3
# Alternate : selsort \${array[*]}
# Output : \${SORTEDARRAY[*]}
# Sorts in DESCENDING ORDER LEXICAL
selsortlexrev(){
local i m x j t
SORTEDARRAY=("\$@")
for (( i=0; i < \${#SORTEDARRAY[@]}; i++ )); do
(( m=i ))
x="\${SORTEDARRAY[m]}" # The minimum value
for (( j=i+1; j < \${#SORTEDARRAY[@]}; j++ )); do
compare LEX "\${SORTEDARRAY[j]}" \$x
(( \$? == 3 )) || continue
(( m=j ))
x="\${SORTEDARRAY[j]}"
done

# Swap if needed
(( m == i )) && continue
t="\${SORTEDARRAY[m]}" # Placeholder for swapping elements
SORTEDARRAY[m]="\${SORTEDARRAY[i]}"
SORTEDARRAY[i]="\$t"
done
}

### FILE SIZE SORTING
##
# selsortsize():   (Selection Sort)
# Worst-case:  Ξ©(N^2) (slow)
# Stability:   stable
# Sensitivity: insensitive
# Use:         Quickly find extrema for unordered data
# Called as: selsort FILE1 FILE2 FILE3
# Alternate : selsort \${array[*]}
# Output : \${SORTEDARRAY[*]}
# Sorts in ASCENDING ORDER FILESIZE
selsortsize(){
local i m x j t
SORTEDARRAY=("\$@")
for (( i=0; i < \${#SORTEDARRAY[@]}; i++ )); do
(( m=i ))
x="\${SORTEDARRAY[m]}" # The minimum value
for (( j=i+1; j < \${#SORTEDARRAY[@]}; j++ )); do
compare SIZE "\${SORTEDARRAY[j]}" \$x
(( \$? == 2 )) || continue
(( m=j ))
x="\${SORTEDARRAY[j]}"
done

# Swap if needed
(( m == i )) && continue
t="\${SORTEDARRAY[m]}" # Placeholder for swapping elements
SORTEDARRAY[m]="\${SORTEDARRAY[i]}"
SORTEDARRAY[i]="\$t"
done
}

# selsortsizerev():   (Selection Sort)
# Worst-case:  Ξ©(N^2) (slow)
# Stability:   stable
# Sensitivity: insensitive
# Use:         Quickly find extrema for unordered data
# Called as: selsort FILE1 FILE2 FILE3
# Alternate : selsort \${array[*]}
# Output : \${SORTEDARRAY[*]}
# Sorts in DESCENDING ORDER FILESIZE
selsortsizerev(){
local i m x j t
SORTEDARRAY=("\$@")
for (( i=0; i < \${#SORTEDARRAY[@]}; i++ )); do
(( m=i ))
x="\${SORTEDARRAY[m]}" # The minimum value
for (( j=i+1; j < \${#SORTEDARRAY[@]}; j++ )); do
compare SIZE "\${SORTEDARRAY[j]}" \$x
(( \$? == 3 )) || continue
(( m=j ))
x="\${SORTEDARRAY[j]}"
done

# Swap if needed
(( m == i )) && continue
t="\${SORTEDARRAY[m]}" # Placeholder for swapping elements
SORTEDARRAY[m]="\${SORTEDARRAY[i]}"
SORTEDARRAY[i]="\$t"
done
}

``````
``````
# Necessary
source MOD.Compare.bsh

##
# numerical minimum
# Input : numbers
# Call : min 3 5 2 6 1 3 5 7
# Returns : The \$ARRAYMIN variable will get the value of the smallest number
min() {
ARRAYMIN="\$1"
while [[ \$2 ]]; do
compare "\$ARRAYMIN" "\$2"
(( \$? == 3 )) && ARRAYMIN="\$2"
shift
done
}

##
# lexical minimum
# Input : words / strings
# Call : minlex panos manos bananos
# Returns : The \$ARRAYMIN variable will get the value of the smallest string
minlex() {
ARRAYMIN="\$1"
while [[ \$2 ]]; do
compare LEX "\$ARRAYMIN" "\$2"
(( \$? == 3 )) && ARRAYMIN="\$2"
shift
done
}

##
# size minimum
# Input : filename1 filename2 filename3 ....
# Call : minlex panos manos bananos
# Returns : The \$ARRAYMIN variable will get the value of the smallest string
minsize() {
ARRAYMIN="\$1"
while [[ \$2 ]]; do
compare SIZE "\$ARRAYMIN" "\$2"
(( \$? == 3 )) && ARRAYMIN="\$2"
shift
done
}

##
# max():
# Set the value of ARRAYMAX to the largest word in the input list.
max() {
ARRAYMAX="\$1"
while [[ \$2 ]]; do
compare "\$ARRAYMAX" "\$2"
(( \$? == 2 )) && ARRAYMAX="\$2"
shift
done
}

maxlex() {
ARRAYMAX="\$1"
while [[ \$2 ]]; do
compare LEX "\$ARRAYMAX" "\$2"
(( \$? == 2 )) && ARRAYMAX="\$2"
shift
done
}

maxsize() {
ARRAYMAX="\$1"
while [[ \$2 ]]; do
compare SIZE "\$ARRAYMAX" "\$2"
(( \$? == 2 )) && ARRAYMAX="\$2"
shift
done
}

##
# compare():
# Input:   lhs rhs
# Returns: 0 if lhs == rhs; 2 if lhs < rhs; 3 if lhs > rhs; 1 if error
# Use:     Define this function in order to tell the below functions how to
#          compare values. If you don't define it, numeric_cmp will be
#          assumed.
if ! declare -f compare > /dev/null; then
compare() {
numeric_cmp "\$@"
}
fi``````
``````#!/bin/bash

# BASE MODULE - NO NECESSARY SOURCING

##
# compare()
# Input : <option> lhs rhs
# Option can be : NUM, LEX, SIZE
# Use : Depending on option calls equiv function, otherwise reverts to
# numerical
compare() {

# Takes parameters : <option> lhs rhs
# Option can be : NUM, LEX, SIZE

LHS=\$2
RHS=\$3

case \$1 in

"NUM") numeric_cmp \$LHS \$RHS ;;
"LEX") lexical_cmp \$LHS \$RHS ;;
"SIZE") filesize_cmp \$LHS \$RHS ;;
*) numeric_cmp "\$@" ;;

esac

}

##
# numeric_cmp()
# Input: lhs(integer) rhs(integer)
# Returns: 0 if lhs == rhs; 2 if lhs < rhs; 3 if lhs > rhs; 1 if error
# Use:     Default comparison function. See the "Use" for compare().
numeric_cmp() {
(( \$1 == \$2 )) && return 0
(( \$1 <  \$2 )) && return 2
(( \$1  > \$2 )) && return 3
}

##
# lexical_cmp()
# Input:   lhs(string) rhs(string)
# Returns: 0 if lhs == rhs; 2 if lhs < rhs; 3 if lhs > rhs; 1 if error
# Use:     Example lexical (alphabetical) comparison function.
#          See the "Use" for compare().
lexical_cmp() {
[[ \$1 == \$2 ]] && return 0
[[ \$1 <  \$2 ]] && return 2
[[ \$1  > \$2 ]] && return 3
}

##
# filesize_cmp()
# Input:   lhs(filename) rhs(filename)
# Returns: 0 if lhs == rhs; 2 if lhs < rhs; 3 if lhs > rhs; 1 if error
# Use:     Example filesize comparison function. Neither a fast nor a
#          particularly precise implementation, but should work and serve as
#          another example how to make a compare() function.
#          See the "Use" for compare().
filesize_cmp() {
local lhs=\$(du "\$1" | grep -o [0-9])
echo "LHS IS : \$lhs"
local rhs=\$(du "\$2"| grep -o [0-9])
echo "RHS IS : \$rhs"
numeric_cmp "\$lhs" "\$rhs"
}``````
``````# Necessary
source MOD.MinMax.bsh

# BUBBLE SORT
#Bubble sort, sometimes referred to as sinking sort, is a simple sorting algorithm
#that repeatedly steps through the list to be sorted, compares each pair of adjacent
#items and swaps them if they are in the wrong order. The pass through the list is
#repeated until no swaps are needed, which indicates that the list is sorted.
#The algorithm, which is a comparison sort, is named for the way smaller or larger
#elements "bubble" to the top of the list. Although the algorithm is simple, it is
#too slow and impractical for most problems even when compared to insertion sort.
#It can be practical if the input is usually in sorted order but may occasionally
#have some out-of-order elements nearly in position.

# PERFORMANCE
#Bubble sort has worst-case and average complexity both О(n2), where n is the number
#of items being sorted. There exist many sorting algorithms with substantially better
#worst-case or average complexity of O(n log n). Even other О(n2) sorting algorithms,
#such as insertion sort, tend to have better performance than bubble sort.
#Therefore, bubble sort is not a practical sorting algorithm when n is large.
#The only significant advantage that bubble sort has over most other implementations,
#even quicksort, but not insertion sort, is that the ability to detect that the list is
#sorted efficiently is built into the algorithm. When the list is already sorted (best-case),
#the complexity of bubble sort is only O(n). By contrast, most other algorithms,
#even those with better average-case complexity, perform their entire sorting process
#on the set and thus are more complex. However, not only does insertion sort have this
#mechanism too, but it also performs better on a list that is substantially sorted
#(having a small number of inversions).
#Bubble sort should be avoided in the case of large collections. It will not be efficient
#in the case of a reverse-ordered collection.

### NUMERICAL SORTING
##
# bsort():     (Bubble Sort)
# Worst-case:  Ξ©(N^2) (slow)
# Stability:   stable
# Sensitivity: insensitive
# Use: Fastest type of sort for nearly-sorted data.
# Called as: bsort 1 3 4 5 6 3 4 5 6
# Alternate : bsort \${array[*]}
# Alternate call : bsort \${array[@]} OR bsort "\${array[@]}"
# Output : \${SORTEDARRAY[*]}
# Sorts in ASCENDING ORDER / NUMERICAL
bsort() {
SORTEDARRAY=("\$@")
local i j t
for (( i=\${#SORTEDARRAY[@]}-1; i>0; i-- )); do
for (( j=1; j<=i; j++ )); do
# Swap if needed
compare "\${SORTEDARRAY[j-1]}" "\${SORTEDARRAY[j]}"
(( \$? == 3 )) || continue
t="\${SORTEDARRAY[j]}" # Placeholder for swapping elements
SORTEDARRAY[j]="\${SORTEDARRAY[j-1]}"
SORTEDARRAY[j-1]="\$t"
done
done
}

# bsortrev():     (Bubble Sort)
# Worst-case:  Ξ©(N^2) (slow)
# Stability:   stable
# Sensitivity: insensitive
# Use: Fastest type of sort for nearly-sorted data.
# Called as: bsort 1 3 4 5 6 3 4 5 6
# Alternate : bsort \${array[*]}
# Alternate call : bsort \${array[@]} OR bsort "\${array[@]}"
# Output : \${SORTEDARRAY[*]}
# Sorts in DESCENDING ORDER / NUMERICAL
bsortrev() {
SORTEDARRAY=("\$@")
local i j t
for (( i=\${#SORTEDARRAY[@]}-1; i>0; i-- )); do
for (( j=1; j<=i; j++ )); do
# Swap if needed
compare "\${SORTEDARRAY[j-1]}" "\${SORTEDARRAY[j]}"
(( \$? == 2 )) || continue
t="\${SORTEDARRAY[j]}" # Placeholder for swapping elements
SORTEDARRAY[j]="\${SORTEDARRAY[j-1]}"
SORTEDARRAY[j-1]="\$t"
done
done
}

### LEXICAL SORTING
##
# bsort():     (Bubble Sort)
# Worst-case:  Ξ©(N^2) (slow)
# Stability:   stable
# Sensitivity: insensitive
# Use: Fastest type of sort for nearly-sorted data.
# Called as: bsort 1 3 4 5 6 3 4 5 6
# Alternate call : bsort \${array[@]} OR bsort "\${array[@]}"
# Alternate : bsort \${array[*]}
# Output : \${SORTEDARRAY[*]}
# Sorts in ASCENDING ORDER / LEXICAL
bsortlex() {
SORTEDARRAY=("\$@")
local i j t
for (( i=\${#SORTEDARRAY[@]}-1; i>0; i-- )); do
for (( j=1; j<=i; j++ )); do
# Swap if needed
compare LEX "\${SORTEDARRAY[j-1]}" "\${SORTEDARRAY[j]}"
(( \$? == 3 )) || continue
t="\${SORTEDARRAY[j]}" # Placeholder for swapping elements
SORTEDARRAY[j]="\${SORTEDARRAY[j-1]}"
SORTEDARRAY[j-1]="\$t"
done
done
}

# bsort():     (Bubble Sort)
# Worst-case:  Ξ©(N^2) (slow)
# Stability:   stable
# Sensitivity: insensitive
# Use: Fastest type of sort for nearly-sorted data.
# Called as: bsort 1 3 4 5 6 3 4 5 6
# Alternate : bsort \${array[*]}
# Alternate call : bsort \${array[@]} OR bsort "\${array[@]}"
# Output : \${SORTEDARRAY[*]}
# Sorts in DESCENDING ORDER / LEXICAL
bsortlexrev() {
SORTEDARRAY=("\$@")
local i j t
for (( i=\${#SORTEDARRAY[@]}-1; i>0; i-- )); do
for (( j=1; j<=i; j++ )); do
# Swap if needed
compare LEX "\${SORTEDARRAY[j-1]}" "\${SORTEDARRAY[j]}"
(( \$? == 2 )) || continue
t="\${SORTEDARRAY[j]}" # Placeholder for swapping elements
SORTEDARRAY[j]="\${SORTEDARRAY[j-1]}"
SORTEDARRAY[j-1]="\$t"
done
done
}

### FILE SIZE SORTING
##
# bsort():     (Bubble Sort)
# Worst-case:  Ξ©(N^2) (slow)
# Stability:   stable
# Sensitivity: insensitive
# Use: Fastest type of sort for nearly-sorted data.
# Called as: bsort 1 3 4 5 6 3 4 5 6
# Alternate : bsort \${array[*]}
# Alternate call : bsort \${array[@]} OR bsort "\${array[@]}"
# Output : \${SORTEDARRAY[*]}
# Sorts in ASCENDING ORDER / FILE SIZE
bsortsize() {
SORTEDARRAY=("\$@")
local i j t
for (( i=\${#SORTEDARRAY[@]}-1; i>0; i-- )); do
for (( j=1; j<=i; j++ )); do
# Swap if needed
compare SIZE "\${SORTEDARRAY[j-1]}" "\${SORTEDARRAY[j]}"
(( \$? == 3 )) || continue
t="\${SORTEDARRAY[j]}" # Placeholder for swapping elements
SORTEDARRAY[j]="\${SORTEDARRAY[j-1]}"
SORTEDARRAY[j-1]="\$t"
done
done
}

# bsort():     (Bubble Sort)
# Worst-case:  Ξ©(N^2) (slow)
# Stability:   stable
# Sensitivity: insensitive
# Use: Fastest type of sort for nearly-sorted data.
# Called as: bsort 1 3 4 5 6 3 4 5 6
# Alternate : bsort \${array[*]}
# Alternate call : bsort \${array[@]} OR bsort "\${array[@]}"
# Output : \${SORTEDARRAY[*]}
# Sorts in DESCENDING ORDER / FILE SIZE
bsortsizerev() {
SORTEDARRAY=("\$@")
local i j t
for (( i=\${#SORTEDARRAY[@]}-1; i>0; i-- )); do
for (( j=1; j<=i; j++ )); do
# Swap if needed
compare SIZE "\${SORTEDARRAY[j-1]}" "\${SORTEDARRAY[j]}"
(( \$? == 2 )) || continue
t="\${SORTEDARRAY[j]}" # Placeholder for swapping elements
SORTEDARRAY[j]="\${SORTEDARRAY[j-1]}"
SORTEDARRAY[j-1]="\$t"
done
done
}

``````
``````# Necessary
source MOD.MinMax.bsh

# BUBBLE SORT
#Bubble sort, sometimes referred to as sinking sort, is a simple sorting algorithm
#that repeatedly steps through the list to be sorted, compares each pair of adjacent
#items and swaps them if they are in the wrong order. The pass through the list is
#repeated until no swaps are needed, which indicates that the list is sorted.
#The algorithm, which is a comparison sort, is named for the way smaller or larger
#elements "bubble" to the top of the list. Although the algorithm is simple, it is
#too slow and impractical for most problems even when compared to insertion sort.
#It can be practical if the input is usually in sorted order but may occasionally
#have some out-of-order elements nearly in position.

# PERFORMANCE
#Bubble sort has worst-case and average complexity both О(n2), where n is the number
#of items being sorted. There exist many sorting algorithms with substantially better
#worst-case or average complexity of O(n log n). Even other О(n2) sorting algorithms,
#such as insertion sort, tend to have better performance than bubble sort.
#Therefore, bubble sort is not a practical sorting algorithm when n is large.
#The only significant advantage that bubble sort has over most other implementations,
#even quicksort, but not insertion sort, is that the ability to detect that the list is
#sorted efficiently is built into the algorithm. When the list is already sorted (best-case),
#the complexity of bubble sort is only O(n). By contrast, most other algorithms,
#even those with better average-case complexity, perform their entire sorting process
#on the set and thus are more complex. However, not only does insertion sort have this
#mechanism too, but it also performs better on a list that is substantially sorted
#(having a small number of inversions).
#Bubble sort should be avoided in the case of large collections. It will not be efficient
#in the case of a reverse-ordered collection.

# Additional Info
#Although bubble sort is one of the simplest sorting algorithms to understand and implement,
#its O(n2) complexity means that its efficiency decreases dramatically on lists of more than
#a small number of elements. Even among simple O(n2) sorting algorithms, algorithms like
#insertion sort are usually considerably more efficient.
#Due to its simplicity, bubble sort is often used to introduce the concept of an algorithm,
#or a sorting algorithm, to introductory computer science students. However, some researchers
#such as Owen Astrachan have gone to great lengths to disparage bubble sort and its continued
#popularity in computer science education, recommending that it no longer even be taught.
#The Jargon File, which famously calls bogosort "the archetypical [sic] perversely awful algorithm",
#also calls bubble sort "the generic bad algorithm". Donald Knuth, in his famous book The Art
#of Computer Programming, concluded that "the bubble sort seems to have nothing to recommend it,
#except a catchy name and the fact that it leads to some interesting theoretical problems",
#some of which he then discusses.
#Bubble sort is asymptotically equivalent in running time to insertion sort in the worst case,
#but the two algorithms differ greatly in the number of swaps necessary. Experimental results such
#as those of Astrachan have also shown that insertion sort performs considerably better even on
#random lists. For these reasons many modern algorithm textbooks avoid using the bubble sort
#algorithm in favor of insertion sort.
#Bubble sort also interacts poorly with modern CPU hardware. It requires at least twice as many writes
#as insertion sort, twice as many cache misses, and asymptotically more branch mispredictions.
#Experiments by Astrachan sorting strings in Java show bubble sort to be roughly one-fifth as fast as
#an insertion sort and 70% as fast as a selection sort.
#In computer graphics it is popular for its capability to detect a very small error (like swap of
#just two elements) in almost-sorted arrays and fix it with just linear complexity (2n). For example,
#it is used in a polygon filling algorithm, where bounding lines are sorted by their x coordinate at
#a specific scan line (a line parallel to x axis) and with incrementing y their order changes
#(two elements are swapped) only at intersections of two lines. Bubble sort is a stable sort algorithm,
#like insertion sort.

## NUMERICAL SORTING
# bsmart(): (Sensitive, fast Bubble Sort variant)
# Use:      quickly reduces the bounds of the bubblesort input list to sort as
#           little as possible -- even better than bsort for nearly-sorted data.
bsmart() {
SORTEDARRAY=("\$@")
local start= i new_start new_end j t
(( i=\${#SORTEDARRAY[@]}-1 ))
while [[ 1 ]]; do
new_start= # New start index of the bubbling scan
new_end=   # New end index of the bubbling scan
for (( j=start>0?start:1; j<=i; j++ )); do
# Swap if needed
compare "\${SORTEDARRAY[j-1]}" "\${SORTEDARRAY[j]}"
(( \$? == 3 )) || continue
t="\${SORTEDARRAY[j]}" # Placeholder for swapping elements
SORTEDARRAY[j]="\${SORTEDARRAY[j-1]}"
SORTEDARRAY[j-1]="\$t"
(( new_end=j-1 ))
new_start="\${new_start:-\$new_end}"
done
[[ \$new_start ]] || break # No swaps: we're done.
i=\$new_end
start=\$new_start
done
}

##
# bsmartrev(): (Sensitive, fast Bubble Sort variant)
# Use:      quickly reduces the bounds of the bubblesort input list to sort as
#           little as possible -- even better than bsort for nearly-sorted data.
# Function : Reverse operations
bsmartrev() {
SORTEDARRAY=("\$@")
local start= i new_start new_end j t
(( i=\${#SORTEDARRAY[@]}-1 ))
while [[ 1 ]]; do
new_start= # New start index of the bubbling scan
new_end=   # New end index of the bubbling scan
for (( j=start>0?start:1; j<=i; j++ )); do
# Swap if needed
compare "\${SORTEDARRAY[j-1]}" "\${SORTEDARRAY[j]}"
(( \$? == 2 )) || continue
t="\${SORTEDARRAY[j]}" # Placeholder for swapping elements
SORTEDARRAY[j]="\${SORTEDARRAY[j-1]}"
SORTEDARRAY[j-1]="\$t"
(( new_end=j-1 ))
new_start="\${new_start:-\$new_end}"
done
[[ \$new_start ]] || break # No swaps: we're done.
i=\$new_end
start=\$new_start
done
}

### LEXICAL SORTING
##

# bsmartlex(): (Sensitive, fast Bubble Sort variant)
# Use:      quickly reduces the bounds of the bubblesort input list to sort as
#           little as possible -- even better than bsort for nearly-sorted data.
bsmartlex() {
SORTEDARRAY=("\$@")
local start= i new_start new_end j t
(( i=\${#SORTEDARRAY[@]}-1 ))
while [[ 1 ]]; do
new_start= # New start index of the bubbling scan
new_end=   # New end index of the bubbling scan
for (( j=start>0?start:1; j<=i; j++ )); do
# Swap if needed
compare LEX "\${SORTEDARRAY[j-1]}" "\${SORTEDARRAY[j]}"
(( \$? == 3 )) || continue
t="\${SORTEDARRAY[j]}" # Placeholder for swapping elements
SORTEDARRAY[j]="\${SORTEDARRAY[j-1]}"
SORTEDARRAY[j-1]="\$t"
(( new_end=j-1 ))
new_start="\${new_start:-\$new_end}"
done
[[ \$new_start ]] || break # No swaps: we're done.
i=\$new_end
start=\$new_start
done
}

##
# bsmartlexrev(): (Sensitive, fast Bubble Sort variant)
# Use:      quickly reduces the bounds of the bubblesort input list to sort as
#           little as possible -- even better than bsort for nearly-sorted data.
# Function : Reverse operations
bsmartlexrev() {
SORTEDARRAY=("\$@")
local start= i new_start new_end j t
(( i=\${#SORTEDARRAY[@]}-1 ))
while [[ 1 ]]; do
new_start= # New start index of the bubbling scan
new_end=   # New end index of the bubbling scan
for (( j=start>0?start:1; j<=i; j++ )); do
# Swap if needed
compare LEX "\${SORTEDARRAY[j-1]}" "\${SORTEDARRAY[j]}"
(( \$? == 2 )) || continue
t="\${SORTEDARRAY[j]}" # Placeholder for swapping elements
SORTEDARRAY[j]="\${SORTEDARRAY[j-1]}"
SORTEDARRAY[j-1]="\$t"
(( new_end=j-1 ))
new_start="\${new_start:-\$new_end}"
done
[[ \$new_start ]] || break # No swaps: we're done.
i=\$new_end
start=\$new_start
done
}

### FILE SIZE SORTING
##

# bsmartsize(): (Sensitive, fast Bubble Sort variant)
# Use:      quickly reduces the bounds of the bubblesort input list to sort as
#           little as possible -- even better than bsort for nearly-sorted data.
bsmartsize() {
SORTEDARRAY=("\$@")
local start= i new_start new_end j t
(( i=\${#SORTEDARRAY[@]}-1 ))
while [[ 1 ]]; do
new_start= # New start index of the bubbling scan
new_end=   # New end index of the bubbling scan
for (( j=start>0?start:1; j<=i; j++ )); do
# Swap if needed
compare SIZE "\${SORTEDARRAY[j-1]}" "\${SORTEDARRAY[j]}"
(( \$? == 3 )) || continue
t="\${SORTEDARRAY[j]}" # Placeholder for swapping elements
SORTEDARRAY[j]="\${SORTEDARRAY[j-1]}"
SORTEDARRAY[j-1]="\$t"
(( new_end=j-1 ))
new_start="\${new_start:-\$new_end}"
done
[[ \$new_start ]] || break # No swaps: we're done.
i=\$new_end
start=\$new_start
done
}

# bsmartlex(): (Sensitive, fast Bubble Sort variant)
# Use:      quickly reduces the bounds of the bubblesort input list to sort as
#           little as possible -- even better than bsort for nearly-sorted data.
bsmartsizerev() {
SORTEDARRAY=("\$@")
local start= i new_start new_end j t
(( i=\${#SORTEDARRAY[@]}-1 ))
while [[ 1 ]]; do
new_start= # New start index of the bubbling scan
new_end=   # New end index of the bubbling scan
for (( j=start>0?start:1; j<=i; j++ )); do
# Swap if needed
compare SIZE "\${SORTEDARRAY[j-1]}" "\${SORTEDARRAY[j]}"
(( \$? == 2 )) || continue
t="\${SORTEDARRAY[j]}" # Placeholder for swapping elements
SORTEDARRAY[j]="\${SORTEDARRAY[j-1]}"
SORTEDARRAY[j-1]="\$t"
(( new_end=j-1 ))
new_start="\${new_start:-\$new_end}"
done
[[ \$new_start ]] || break # No swaps: we're done.
i=\$new_end
start=\$new_start
done
}``````
``````# Necessary
source MOD.MinMax.bsh

# INSERTION SORT

#Insertion sort is a simple sorting algorithm that builds the final sorted array
#(or list) one item at a time. It is much less efficient on large lists than more
#advanced algorithms such as quicksort, heapsort, or merge sort. However, insertion
#sort provides several advantages:

#Simple implementation: Bentley shows a three-line C version, and a five-line optimized version:116
#Efficient for (quite) small data sets, much like other quadratic sorting algorithms
#More efficient in practice than most other simple quadratic (i.e., O(n2)) algorithms such as selection sort or bubble sort
#Adaptive, i.e., efficient for data sets that are already substantially sorted: the time complexity is O(nk) when each element in the input is no more than k places away from its sorted position
#Stable; i.e., does not change the relative order of elements with equal keys
#In-place; i.e., only requires a constant amount O(1) of additional memory space
#Online; i.e., can sort a list as it receives it

# ALGORITHM AND PERFORMANCE
#Insertion sort iterates, consuming one input element each repetition, and growing a
#sorted output list. Each iteration, insertion sort removes one element from the input data,
#finds the location it belongs within the sorted list, and inserts it there. It repeats until
#no input elements remain.
#Sorting is typically done in-place, by iterating up the array, growing the sorted list behind it.
#At each array-position, it checks the value there against the largest value in the sorted list
#(which happens to be next to it, in the previous array-position checked). If larger, it leaves
#the element in place and moves to the next. If smaller, it finds the correct position within the
#sorted list, shifts all the larger values up to make a space, and inserts into that correct position.
#The resulting array after k iterations has the property where the first k + 1 entries are
#sorted ("+1" because the first entry is skipped). In each iteration the first remaining entry of
#the input is removed, and inserted into the result at the correct position, thus extending the result:

#Array prior to the insertion of x

#becomes

#Array after the insertion of x

#with each element greater than x copied to the right as it is compared against x.

#The most common variant of insertion sort, which operates on arrays, can be described as follows:

#Suppose there exists a function called Insert designed to insert a value into a sorted sequence at
#the beginning of an array. It operates by beginning at the end of the sequence and shifting each
#element one place to the right until a suitable position is found for the new element. The function
#has the side effect of overwriting the value stored immediately after the sorted sequence in the array.
#To perform an insertion sort, begin at the left-most element of the array and invoke Insert to insert
#each element encountered into its correct position. The ordered sequence into which the element is
#inserted is stored at the beginning of the array in the set of indices already examined. Each
#insertion overwrites a single value: the value being inserted.

##
# insort():    (Insertion Sort)
# Worst-case:  Ξ©(N^2) (slow)
# Stability:   stable
# Sensitivity: insensitive
# Use: Fastest type of sort for nearly-sorted data.
insort() {
SORTEDARRAY=("\$@")
local i m x j
for (( i=0; i<\${#SORTEDARRAY[@]}; i++ )); do
m="\$i"                # Final index for the minimum element
x="\${SORTEDARRAY[m]}" # Minimum value
for (( j=i+1; j<\${#SORTEDARRAY[@]}; j++ )); do
compare "\${SORTEDARRAY[j]}" \$x
(( \$? == 2 )) || continue
m="\$j"
x="\${SORTEDARRAY[j]}"
done
# Insert the m'th element at i, and move i and everything following it up
# one.
for (( j=m; j>i; j-- )); do
SORTEDARRAY[j]="\${SORTEDARRAY[j-1]}"
done
SORTEDARRAY[i]="\$x"
done
}

##
# insortrev():    (Insertion Sort)
# Worst-case:  Ξ©(N^2) (slow)
# Stability:   stable
# Sensitivity: insensitive
# Use: Fastest type of sort for nearly-sorted data.
insortrev() {
SORTEDARRAY=("\$@")
local i m x j
for (( i=0; i<\${#SORTEDARRAY[@]}; i++ )); do
m="\$i"                # Final index for the minimum element
x="\${SORTEDARRAY[m]}" # Minimum value
for (( j=i+1; j<\${#SORTEDARRAY[@]}; j++ )); do
compare "\${SORTEDARRAY[j]}" \$x
(( \$? == 3 )) || continue
m="\$j"
x="\${SORTEDARRAY[j]}"
done
# Insert the m'th element at i, and move i and everything following it up
# one.
for (( j=m; j>i; j-- )); do
SORTEDARRAY[j]="\${SORTEDARRAY[j-1]}"
done
SORTEDARRAY[i]="\$x"
done
}

##
# insortlex():    (Insertion Sort)
# Worst-case:  Ξ©(N^2) (slow)
# Stability:   stable
# Sensitivity: insensitive
# Use: Fastest type of sort for nearly-sorted data.
insortlex() {
SORTEDARRAY=("\$@")
local i m x j
for (( i=0; i<\${#SORTEDARRAY[@]}; i++ )); do
m="\$i"                # Final index for the minimum element
x="\${SORTEDARRAY[m]}" # Minimum value
for (( j=i+1; j<\${#SORTEDARRAY[@]}; j++ )); do
compare LEX "\${SORTEDARRAY[j]}" \$x
(( \$? == 2 )) || continue
m="\$j"
x="\${SORTEDARRAY[j]}"
done
# Insert the m'th element at i, and move i and everything following it up
# one.
for (( j=m; j>i; j-- )); do
SORTEDARRAY[j]="\${SORTEDARRAY[j-1]}"
done
SORTEDARRAY[i]="\$x"
done
}

##
# insortlexrev():    (Insertion Sort)
# Worst-case:  Ξ©(N^2) (slow)
# Stability:   stable
# Sensitivity: insensitive
# Use: Fastest type of sort for nearly-sorted data.
insortlexrev() {
SORTEDARRAY=("\$@")
local i m x j
for (( i=0; i<\${#SORTEDARRAY[@]}; i++ )); do
m="\$i"                # Final index for the minimum element
x="\${SORTEDARRAY[m]}" # Minimum value
for (( j=i+1; j<\${#SORTEDARRAY[@]}; j++ )); do
compare LEX "\${SORTEDARRAY[j]}" \$x
(( \$? == 3 )) || continue
m="\$j"
x="\${SORTEDARRAY[j]}"
done
# Insert the m'th element at i, and move i and everything following it up
# one.
for (( j=m; j>i; j-- )); do
SORTEDARRAY[j]="\${SORTEDARRAY[j-1]}"
done
SORTEDARRAY[i]="\$x"
done
}

##
# insortsize():    (Insertion Sort)
# Worst-case:  Ξ©(N^2) (slow)
# Stability:   stable
# Sensitivity: insensitive
# Use: Fastest type of sort for nearly-sorted data.
insortsize() {
SORTEDARRAY=("\$@")
local i m x j
for (( i=0; i<\${#SORTEDARRAY[@]}; i++ )); do
m="\$i"                # Final index for the minimum element
x="\${SORTEDARRAY[m]}" # Minimum value
for (( j=i+1; j<\${#SORTEDARRAY[@]}; j++ )); do
compare SIZE "\${SORTEDARRAY[j]}" \$x
(( \$? == 2 )) || continue
m="\$j"
x="\${SORTEDARRAY[j]}"
done
# Insert the m'th element at i, and move i and everything following it up
# one.
for (( j=m; j>i; j-- )); do
SORTEDARRAY[j]="\${SORTEDARRAY[j-1]}"
done
SORTEDARRAY[i]="\$x"
done
}

##
# insortsizerev():    (Insertion Sort)
# Worst-case:  Ξ©(N^2) (slow)
# Stability:   stable
# Sensitivity: insensitive
# Use: Fastest type of sort for nearly-sorted data.
insortsizerev() {
SORTEDARRAY=("\$@")
local i m x j
for (( i=0; i<\${#SORTEDARRAY[@]}; i++ )); do
m="\$i"                # Final index for the minimum element
x="\${SORTEDARRAY[m]}" # Minimum value
for (( j=i+1; j<\${#SORTEDARRAY[@]}; j++ )); do
compare SIZE "\${SORTEDARRAY[j]}" \$x
(( \$? == 3 )) || continue
m="\$j"
x="\${SORTEDARRAY[j]}"
done
# Insert the m'th element at i, and move i and everything following it up
# one.
for (( j=m; j>i; j-- )); do
SORTEDARRAY[j]="\${SORTEDARRAY[j-1]}"
done
SORTEDARRAY[i]="\$x"
done
}
``````
``````1. Mod.Compare          :    Library for Comparison(Numerical, lexical, files)
2. Mod.BubbleSort       :    Library for Bubblesort(Numerical, lexical, files)
3. Mod.MinMax           :    Library for MinMax Functions
4. Mod.InsertionSort    :    Library for Bubblesort(Numerical, lexical, files)
5. Mod.SelectionSort    :    Library for SelectionSort(N/L/F)
6. Mod.SmartBubbleSort  :    Library for Smart Bubble Sort (N/L/F)``````
``````################################
###############################

#!/bin/bash

##
#
# ARRAY FUNCTIONS
# Various functions for bash arrays -- mostly reimplementations from
# "Mastering Algorithms in Perl"
# Reimplemented by: Michael A. Smith, aka kojiro, <michael at smith dash li
#                                                  dot com>
#
# Last Modified: 2009-10-10
# Usage and comments: You can just source the file to get access to the
# functions in your script. If you want to test some functions,
# ./sort.bash -t funclist
#
# This code is released AS-IS, under an MIT license. The MIT license can be
# found at http://www.opensource.org/licenses/mit-license.php and is included
# for your convenience at the bottom of this file.
##

##
#
# Utility algorithms
#
##

##
# numeric_cmp()
# Input: lhs(integer) rhs(integer)
# Returns: 0 if lhs == rhs; 2 if lhs < rhs; 3 if lhs > rhs; 1 if error
# Use:     Default comparison function. See the "Use" for compare().
numeric_cmp() {
(( \$1 == \$2 )) && return 0
(( \$1 <  \$2 )) && return 2
(( \$1  > \$2 )) && return 3
}

##
# lexical_cmp()
# Input:   lhs(string) rhs(string)
# Returns: 0 if lhs == rhs; 2 if lhs < rhs; 3 if lhs > rhs; 1 if error
# Use:     Example lexical (alphabetical) comparison function.
#          See the "Use" for compare().
lexical_cmp() {
[[ \$1 == \$2 ]] && return 0
[[ \$1 <  \$2 ]] && return 2
[[ \$1  > \$2 ]] && return 3
}

##
# filesize_cmp()
# Input:   lhs(filename) rhs(filename)
# Returns: 0 if lhs == rhs; 2 if lhs < rhs; 3 if lhs > rhs; 1 if error
# Use:     Example filesize comparison function. Neither a fast nor a
#          particularly precise implementation, but should work and serve as
#          another example how to make a compare() function.
#          See the "Use" for compare().
filesize_cmp() {
local lhs=\$(du "\$1")
local rhs=\$(du "\$2")
numeric_cmp "\$lhs" "\$rhs"
}

##
# compare():
# Input:   lhs rhs
# Returns: 0 if lhs == rhs; 2 if lhs < rhs; 3 if lhs > rhs; 1 if error
# Use:     Define this function in order to tell the below functions how to
#          compare values. If you don't define it, numeric_cmp will be
#          assumed.
if ! declare -f compare > /dev/null; then
compare() {
numeric_cmp "\$@"
}
fi

##
# splice():
# Input: offset length array-to-splice
# var:   set the variable SPLICEINPUT prior to calling
# Use:   Removes the elements designated by offset and length from an array,
#        and replaces them with the elements of SPLICEINPUT, if any.
splice() {
local offset=\$1
local length=\$2
shift 2
SPLICEARRAY=("\$@")
local -a backarray
local i
for (( i=\${#SPLICEARRAY[@]}; i>=offset; i-- )); do
(( i>=offset+length )) && backarray[i]="\${SPLICEARRAY[i]}"
unset SPLICEARRAY[i]
done
SPLICEARRAY+=("\${SPLICEINPUT[@]}" "\${backarray[@]}")
}

##
#
# Min/Max: Straightforward one-pass extrema searches
# Input:   Word list
# Output:  Scalar global variable
#
##

##
# min():
# Set the value of ARRAYMIN to the smallest word in the input list.
min() {
ARRAYMIN="\$1"
while [[ \$2 ]]; do
compare "\$ARRAYMIN" "\$2"
(( \$? == 3 )) && ARRAYMIN="\$2"
shift
done
}

##
# max():
# Set the value of ARRAYMAX to the largest word in the input list.
max() {
ARRAYMAX="\$1"
while [[ \$2 ]]; do
compare "\$ARRAYMAX" "\$2"
(( \$? == 2 )) && ARRAYMAX="\$2"
shift
done
}

##
#
# Sort Algorithms
# Input:  Word list
# Output: Global array variable SORTEDARRAY
#
##

##
# selsort():   (Selection Sort)
# Worst-case:  Ξ©(N^2) (slow)
# Stability:   stable
# Sensitivity: insensitive
# Use:         Quickly find extrema for unordered data
selsort() {
local i m x j t
SORTEDARRAY=("\$@")
for (( i=0; i < \${#SORTEDARRAY[@]}; i++ )); do
(( m=i ))
x="\${SORTEDARRAY[m]}" # The minimum value
for (( j=i+1; j < \${#SORTEDARRAY[@]}; j++ )); do
compare "\${SORTEDARRAY[j]}" x
(( \$? == 2 )) || continue
(( m=j ))
x="\${SORTEDARRAY[j]}"
done

# Swap if needed
(( m == i )) && continue
t="\${SORTEDARRAY[m]}" # Placeholder for swapping elements
SORTEDARRAY[m]="\${SORTEDARRAY[i]}"
SORTEDARRAY[i]="\$t"
done
}

##
# bsort():     (Bubble Sort)
# Worst-case:  Ξ©(N^2) (slow)
# Stability:   stable
# Sensitivity: insensitive
# Use: Fastest type of sort for nearly-sorted data.
bsort() {
SORTEDARRAY=("\$@")
local i j t
for (( i=\${#SORTEDARRAY[@]}-1; i>0; i-- )); do
for (( j=1; j<=i; j++ )); do
# Swap if needed
compare "\${SORTEDARRAY[j-1]}" "\${SORTEDARRAY[j]}"
(( \$? == 3 )) || continue
t="\${SORTEDARRAY[j]}" # Placeholder for swapping elements
SORTEDARRAY[j]="\${SORTEDARRAY[j-1]}"
SORTEDARRAY[j-1]="\$t"
done
done
}

##
# bsmart(): (Sensitive, fast Bubble Sort variant)
# Use:      quickly reduces the bounds of the bubblesort input list to sort as
#           little as possible -- even better than bsort for nearly-sorted data.
bsmart() {
SORTEDARRAY=("\$@")
local start= i new_start new_end j t
(( i=\${#SORTEDARRAY[@]}-1 ))
while [[ 1 ]]; do
new_start= # New start index of the bubbling scan
new_end=   # New end index of the bubbling scan
for (( j=start>0?start:1; j<=i; j++ )); do
# Swap if needed
compare "\${SORTEDARRAY[j-1]}" "\${SORTEDARRAY[j]}"
(( \$? == 3 )) || continue
t="\${SORTEDARRAY[j]}" # Placeholder for swapping elements
SORTEDARRAY[j]="\${SORTEDARRAY[j-1]}"
SORTEDARRAY[j-1]="\$t"
(( new_end=j-1 ))
new_start="\${new_start:-\$new_end}"
done
[[ \$new_start ]] || break # No swaps: we're done.
i=\$new_end
start=\$new_start
done
}

##
# insort():    (Insertion Sort)
# Worst-case:  Ξ©(N^2) (slow)
# Stability:   stable
# Sensitivity: insensitive
# Use: Fastest type of sort for nearly-sorted data.
insort() {
SORTEDARRAY=("\$@")
local i m x j
for (( i=0; i<\${#SORTEDARRAY[@]}; i++ )); do
m="\$i"                # Final index for the minimum element
x="\${SORTEDARRAY[m]}" # Minimum value
for (( j=i+1; j<\${#SORTEDARRAY[@]}; j++ )); do
compare "\${SORTEDARRAY[j]}" x
(( \$? == 2 )) || continue
m="\$j"
x="\${SORTEDARRAY[j]}"
done
# Insert the m'th element at i, and move i and everything following it up
# one.
for (( j=m; j>i; j-- )); do
SORTEDARRAY[j]="\${SORTEDARRAY[j-1]}"
done
SORTEDARRAY[i]="\$x"
done
}

##
# shellsort(): (Shell Sort)
# Worst-case:  Ξ©(N((log N)/(log log N))^2)
#              (can be fast, but sensitive to input data)
# Stability:   stable
# Sensitivity: sensitive
shellsort() {
SORTEDARRAY=("\$@")
local shell i j t
for (( shell=1; shell<\${#SORTEDARRAY[@]}; 1 )); do
(( shell=2*shell+1 )) # Just let the shell grow.
done

while [[ 1 ]]; do
(( shell=(shell-1)/2 ))
for (( i=shell; i<\${#SORTEDARRAY[@]}; i++)); do
for (( j=i-shell; j>=0; j-=shell )); do
compare "\${SORTEDARRAY[j]}" "\${SORTEDARRAY[j+shell]}"
(( \$? == 3 )) || break
t="\${SORTEDARRAY[j]}"
SORTEDARRAY[j]="\${SORTEDARRAY[j+shell]}"
SORTEDARRAY[j+shell]="\$t"
done
done
(( shell > 1 )) || break
done
}

##
# msort():     (Merge sort)
# Average:     ΞΈ(N(log N)) (pretty fast)
# Stability:   stable
# Sensitivity: insensitive to the key distribution of the input
# Drawbacks:   Requires temporary space equal in size to the input array.
# msort will use recursion by default -- msort_iter is additionally provided.
msort() {
SORTEDARRAY=("\$@")
msort_recurse 0 \$((\${#@}-1))
unset msortWrkArr
}
msort_recurse()	{
local first=\$1
local last=\$2
shift 2
(( last > first )) || return 0
local middle
(( middle=(last+first)/2 ))
msort_recurse \$first \$middle "\${SORTEDARRAY[@]}"
msort_recurse \$(( middle+1 )) \$last "\${SORTEDARRAY[@]}"
merge \$first \$middle \$last "\${SORTEDARRAY[@]}"
}
declare -a msortWrkArr # Global work array
unset msortWrkArr
merge() {
local first=\$1
local middle=\$2
local last=\$3
shift 3
local n i j n1
(( n=last-first+1 ))

# Initialize msortWrkArr with relevant elements from the array
for (( i=first, j=0; i<=last; )); do
msortWrkArr[j++]="\${SORTEDARRAY[i++]}"
done

# Actual merge. Proceed through msortWrkArr[] and copy elements in order back to
# SORTEDARRAY[]. \$i is index for the merge result, \$j is index in first half
# of the working copy, \$k is index in second half.
(( middle>last )) && (( middle=(first+last)/2 ))
(( n1=middle-first+1 )) # Size of first half
for (( i=first, j=0, k=n1; i<=last; i++ )); do
if {
(( j < n1 )) && {
(( k == n )) || {
compare "\${msortWrkArr[j]}" "\${msortWrkArr[k]}";
(( \$? == 2 ))
}
}
}; then
SORTEDARRAY[i]="\${msortWrkArr[j++]}"
else
SORTEDARRAY[i]="\${msortWrkArr[k++]}"
fi
done
}
msort_iter() {
SORTEDARRAY=("\$@")
local N Nt2 Nm1 first middle last
(( N=\${#SORTEDARRAY[@]},
Nt2=N*2,
Nm1=N-1
))
for (( size=2; size<Nt2; size*=2 )); do
for (( first=0; first<N; first+=size )); do
(( last=first+size-1 ))
(( middle=(first+last)/2 ))
if (( last<N )); then
merge \$first \$middle \$last
else
merge \$first \$middle \$Nm1
fi
done
done
}
##
# hsort():     (Heap sort)
# Average:     ΞΈ(N(log N)) (pretty fast)
# Stability:   unstable
# Uses:        Best sort for certain graph algorithms
hsort() {
local index last t
SORTEDARRAY=("\$@")
for (( index=1+\${#SORTEDARRAY[@]}/2; index--; )); do heapify \$index; done
for (( last=\${#SORTEDARRAY[@]}; --last; )); do
t="\${SORTEDARRAY}"
SORTEDARRAY="\${SORTEDARRAY[last]}"
SORTEDARRAY[last]="\$t"
heapify 0 \$last
done
}
heapify() {
local index last swap high try t
index=\$1 last=\${2:-\${#SORTEDARRAY[@]}}
swap=\$index
(( high=index*2+1 ))
for (( try=index*2; try<last && try<=high; try++ )); do
compare "\${SORTEDARRAY[try]}" "\${SORTEDARRAY[swap]}"
(( \$?==3 )) && swap=\$try
# (( SORTEDARRAY[try]>SORTEDARRAY[swap] )) && swap=\$try
done
if (( swap != index )); then
# The heap is in disorder. Must reshuffle
t="\${SORTEDARRAY[swap]}"
SORTEDARRAY[swap]="\${SORTEDARRAY[index]}"
SORTEDARRAY[index]="\$t"
heapify \$swap \$last
fi
}

##
# qsort():  (Quick sort)
# Average:
# Stability:
# Uses:
qsort() {
SORTEDARRAY=("\$@")
qsort_recurse 0 \$((\${#@}-1))
}
qsort_recurse() {
local -i l r m i j k # left, right, mid bounds and some iterators
local part temp      # partition value and temporary storage
(( l=i=\$1, r=j=\$2, m=(l+r)/2 ))
part="\${SORTEDARRAY[m]}"
while ((j > i)); do
while [[ 1 ]]; do
compare "\${SORTEDARRAY[i]}" "\$part"
(( \$? == 2 && i++ )) || break
done
while [[ 1 ]]; do
compare "\${SORTEDARRAY[j]}" "\$part"
(( \$? == 3 && j-- )) || break
done
if (( i <= j )); then
temp="\${SORTEDARRAY[i]}"
SORTEDARRAY[i]="\${SORTEDARRAY[j]}"
SORTEDARRAY[j]="\$temp"
(( i++, j-- ))
fi
done
(( l<j )) && qsort_recurse \$l \$j
(( r>i )) && qsort_recurse \$i \$r
}

##
#
# Tests: For making sure the above algorithms suck as little as possible.
#
##

if [[ \$1 = -d ]]; then
shift
set -xv
fi
if [[ \$1 = -t && \$2 ]]; then
shift
testrunner() (
while read _ _ f; do
[[ \$f = test_* ]] && unset -f "\$f"
done < <(declare -F)
get_random_array() {
local i j=\${1:-10}
RANDOM=\$(date +%s)
for ((i=0; i<j; i++)); do RANDOM_ARRAY[i]=\$RANDOM; done
}
test_splice() {
local -a SPLICEINPUT=(forty seven twins were born in Santa Barbara)
local -a SPLICEARRAY
splice 4 3 "\${RANDOM_ARRAY[@]}"
echo "Spliced from 4 to +3: \${SPLICEARRAY[@]}"
}
test_selsort() {
local -a SORTEDARRAY
selsort "\${RANDOM_ARRAY[@]}"
echo "Selection Sorted: \${SORTEDARRAY[@]}"
}
test_min() {
local ARRAYMIN
min "\${RANDOM_ARRAY[@]}"
echo "Min: \$ARRAYMIN"
}
test_max() {
local ARRAYMAX
max "\${RANDOM_ARRAY[@]}"
echo "Max: \$ARRAYMAX"
}
test_bsort() {
local -a SORTEDARRAY
bsort "\${RANDOM_ARRAY[@]}"
echo "Bubble Sorted: \${SORTEDARRAY[@]}"
}
test_bsmart() {
local -a SORTEDARRAY
bsmart "\${RANDOM_ARRAY[@]}"
echo "Bubble Smart Sorted: \${SORTEDARRAY[@]}"
}
test_insort() {
local -a SORTEDARRAY
insort "\${RANDOM_ARRAY[@]}"
echo "Insertion Sorted: \${SORTEDARRAY[@]}"
}
test_shellsort() {
local -a SORTEDARRAY
shellsort "\${RANDOM_ARRAY[@]}"
echo "Shell Sorted: \${SORTEDARRAY[@]}"
}
test_msort() {
local -a SORTEDARRAY
msort "\${RANDOM_ARRAY[@]}"
echo "Merge Sorted: \${SORTEDARRAY[@]}"
}
test_msort_iter() {
local -a SORTEDARRAY
msort "\${RANDOM_ARRAY[@]}"
echo "Merge Sorted: \${SORTEDARRAY[@]}"
}
test_hsort() {
local -a SORTEDARRAY
hsort "\${RANDOM_ARRAY[@]}"
echo "Heap Sorted: \${SORTEDARRAY[@]}"
}
test_qsort() {
local -a SORTEDARRAY
qsort "\${RANDOM_ARRAY[@]}"
echo "Quick Sorted: \${SORTEDARRAY[@]}"
}
# Get list of test function names
while [[ \$1 ]]; do
local tested=
while read _ _ func; do
[[ \$func = test_* ]] || continue
if [[ test_\$1 = \$func ]]; then
get_random_array
echo "An array of random numbers: \${RANDOM_ARRAY[@]}"
"\$func"
tested=1
break
fi
done < <(declare -F)
[[ \$tested ]] || echo "test_\$1 is not defined."
shift
done
)
testrunner "\$@"
fi
``````