Cacher is the code snippet organizer for pro developers

#!/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.[1] 
#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.[1] 
#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.[2]
#The Jargon File, which famously calls bogosort "the archetypical [sic] perversely awful algorithm", 
#also calls bubble sort "the generic bad algorithm".[3] 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.[1]
#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.[2]
#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[1]: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[0]}"
		SORTEDARRAY[0]="${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